Capitalize the Title

Easy

#1939Time: O(N), where N is the length of the `title`. The `split` operation, the loop through words (which involves operations like `toLowerCase` and `substring` that are proportional to word length), and building the final string all contribute to a linear time complexity.Space: O(N), where N is the length of the `title`. Space is required for the array of words created by `split()` and for the `StringBuilder` used to construct the output.

Data structures

String

Prompt

You are given a string title consisting of one or more words separated by a single space, where each word consists of English letters. Capitalize the string by changing the capitalization of each word such that:

If the length of the word is 1 or 2 letters, change all letters to lowercase.
Otherwise, change the first letter to uppercase and the remaining letters to lowercase.

Return the capitalized title.

Example 1:

Input: title = "capiTalIze tHe titLe"
Output: "Capitalize The Title"
Explanation:
Since all the words have a length of at least 3, the first letter of each word is uppercase, and the remaining letters are lowercase.

Example 2:

Input: title = "First leTTeR of EACH Word"
Output: "First Letter of Each Word"
Explanation:
The word "of" has length 2, so it is all lowercase.
The remaining words have a length of at least 3, so the first letter of each remaining word is uppercase, and the remaining letters are lowercase.

Example 3:

Input: title = "i lOve leetcode"
Output: "i Love Leetcode"
Explanation:
The word "i" has length 1, so it is lowercase.
The remaining words have a length of at least 3, so the first letter of each remaining word is uppercase, and the remaining letters are lowercase.

Constraints:

1 <= title.length <= 100
title consists of words separated by a single space without any leading or trailing spaces.
Each word consists of uppercase and lowercase English letters and is non-empty.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is straightforward and relies on high-level string functions. It involves splitting the title into words, processing each word individually based on the capitalization rules, and then joining them back into a single string.

Algorithm

Split the title string by spaces to get an array of words.
Initialize a StringBuilder to construct the result.
Loop through each word in the words array.
If word.length() <= 2, append the lowercase version of the word to the StringBuilder.
Otherwise, append the first character of the word in uppercase, followed by the rest of the word in lowercase.
Append a space after each word, except the last one.
Return the final string from the StringBuilder.

Walkthrough

The algorithm first splits the input title string into an array of words using the space character as a delimiter. It then iterates through this array. For each word, it checks its length. If the length is 2 or less, the entire word is converted to lowercase. If the length is 3 or more, the first letter is converted to uppercase and the remaining letters are converted to lowercase. A StringBuilder is used to efficiently build the final string by appending each processed word followed by a space (except for the last word).

1class Solution {2    public String capitalizeTitle(String title) {3        String[] words = title.split(" ");4        StringBuilder result = new StringBuilder();5        for (int i = 0; i < words.length; i++) {6            String word = words[i];7            if (word.length() <= 2) {8                result.append(word.toLowerCase());9            } else {10                result.append(Character.toUpperCase(word.charAt(0)));11                result.append(word.substring(1).toLowerCase());12            }13            if (i < words.length - 1) {14                result.append(" ");15            }16        }17        return result.toString();18    }19}

Complexity

Time

O(N), where N is the length of the `title`. The `split` operation, the loop through words (which involves operations like `toLowerCase` and `substring` that are proportional to word length), and building the final string all contribute to a linear time complexity.

Space

O(N), where N is the length of the `title`. Space is required for the array of words created by `split()` and for the `StringBuilder` used to construct the output.

Trade-offs

Pros

Simple and easy to understand.
Leverages standard library functions, leading to concise code.

Cons

Less memory-efficient due to the creation of an intermediate array of strings.
Involves creating multiple temporary string objects during processing (e.g., from toLowerCase, substring), which can increase garbage collection overhead.

This is a more optimized approach that avoids creating intermediate string arrays and performs the capitalization in a single pass over the string's characters. It modifies a character array representation of the string directly, making it more efficient in terms of both time and memory.

Algorithm

Convert the input title string to a character array chars.
Initialize an index i = 0 to iterate through the string.
Use a for loop that continues as long as i is less than the string length.
Inside the loop, mark the start of a word with wordStart = i.
Use an inner while loop to find the end of the word. In this loop, convert every character to lowercase and advance i.
After the inner loop, the word from wordStart to i-1 has been processed (all lowercase). Check its length (i - wordStart).
If the length is greater than 2, convert the character at chars[wordStart] to uppercase.
The outer loop will naturally advance i past the space to the start of the next word.
After the loop, create and return a new string from the modified chars array.

Walkthrough

The algorithm begins by converting the input title into a character array for efficient modification. It then iterates through this array in a single pass. It uses a pointer i that moves from start to end. When i is at the beginning of a word, it marks that position. Then, an inner loop moves i to the end of that word, converting all its characters to lowercase along the way. Once the word is fully scanned, its length is checked. If the length is greater than 2, the character at the marked start position is capitalized. This process repeats for all words. This single-pass method minimizes object allocations and data copying.

1class Solution {2    public String capitalizeTitle(String title) {3        char[] chars = title.toCharArray();4        int n = chars.length;5        for (int i = 0; i < n; ++i) {6            // Mark the start of a word7            int wordStart = i;8            9            // Iterate to the end of the word10            while (i < n && chars[i] != ' ') {11                // Convert current character to lowercase12                chars[i] = Character.toLowerCase(chars[i]);13                i++;14            }15            16            // After the loop, 'i' is at a space or end of string.17            // The word is from 'wordStart' to 'i - 1'.18            // Check word length and capitalize if needed.19            if (i - wordStart > 2) {20                chars[wordStart] = Character.toUpperCase(chars[wordStart]);21            }22        }23        return new String(chars);24    }25}

Complexity

Time

O(N), where N is the length of the `title`. Although there is a nested loop structure, the outer loop's index `i` is advanced by the inner loop. This ensures that each character of the string is processed only once, resulting in a linear time complexity.

Space

O(N) to store the character array `chars`. Since strings are immutable in Java, a new character array or `StringBuilder` is necessary to perform modifications.

Trade-offs

Pros

Most efficient in terms of time and memory.
Avoids creating intermediate string arrays and objects.
Processes the string in a single pass.

Cons

The logic is slightly more complex, involving manual index management.
Code can be less readable than the high-level split/join approach for those unfamiliar with this pattern.

Solutions

Solution

1public class Solution {2    public string CapitalizeTitle(string title) {3        List < string > ans = new List < string > ();4        foreach(string s in title.Split(' ')) {5            if (s.Length < 3) {6                ans.Add(s.ToLower());7            } else {8                ans.Add(char.ToUpper(s[0]) + s.Substring(1).ToLower());9            }10        }11        return string.Join(" ", ans);12    }13}

1class Solution {2public3  String capitalizeTitle(String title) {4    List<String> ans = new ArrayList<>();5    for (String s : title.split(" ")) {6      if (s.length() < 3) {7        ans.add(s.toLowerCase());8      } else {9        ans.add(s.substring(0, 1).toUpperCase() + s.substring(1).toLowerCase());10      }11    }12    return String.join(" ", ans);13  }14}

1class Solution {2public:3  string capitalizeTitle(string title) {4    transform(title.begin(), title.end(), title.begin(), ::tolower);5    istringstream ss(title);6    string ans;7    while (ss >> title) {8      if (title.size() > 2)9        title[0] = toupper(title[0]);10      ans += title;11      ans += " ";12    }13    ans.pop_back();14    return ans;15  }16};

1class Solution:2    def capitalizeTitle(self, title: str) -> str: words = [w . lower() if len(w) < 3 else w . capitalize() for w in title . split()] return " " . join(words)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem