Generate Tag for Video Caption

Easy

#3189Time: `O(N^2)`, where `N` is the length of the caption. The `split` operation takes `O(N)`. The main bottleneck is the string concatenation in a loop. If the final tag has length `L` (where `L` is at most `N`), creating it via repeated concatenation can take `O(L^2)` time because strings are immutable in Java.Space: `O(N^2)` in the worst case. The `words` array takes `O(N)` space. However, the repeated creation of new string objects during concatenation can lead to a high memory footprint from all the intermediate, discarded string objects.

Data structures

String

Prompt

You are given a string caption representing the caption for a video.

The following actions must be performed in order to generate a valid tag for the video:

Combine all words in the string into a single camelCase string prefixed with '#'. A camelCase string is one where the first letter of all words except the first one is capitalized. All characters after the first character in each word must be lowercase.
Remove all characters that are not an English letter, except the first '#'.
Truncate the result to a maximum of 100 characters.

Return the tag after performing the actions on caption.

Example 1:

Input: caption = "Leetcode daily streak achieved"

Output: "#leetcodeDailyStreakAchieved"

Explanation:

The first letter for all words except "leetcode" should be capitalized.

Example 2:

Input: caption = "can I Go There"

Output: "#canIGoThere"

Explanation:

The first letter for all words except "can" should be capitalized.

Example 3:

Input: caption = "hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh"

Output: "#hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh"

Explanation:

Since the first word has length 101, we need to truncate the last two letters from the word.

Constraints:

1 <= caption.length <= 150
caption consists only of English letters and ' '.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach follows the problem description directly. It first splits the caption into words, then iterates through the words, formats them according to camelCase rules, and concatenates them using the + operator. This is a straightforward but inefficient method for building strings in a loop.

Algorithm

Trim leading/trailing whitespace from caption and split it into an array of words using one or more spaces as a delimiter.
Handle the edge case of an empty caption, returning "#" if no words are found.
Initialize a String variable tag with "#" followed by the first word converted to lowercase.
Iterate through the words array starting from the second word (index 1).
For each word, capitalize its first letter and convert the rest to lowercase.
Concatenate this formatted word to the tag string using the += operator.
After the loop, if the length of tag is greater than 100, return the first 100 characters.
Otherwise, return the full tag.

Walkthrough

The algorithm begins by splitting the input caption string by spaces to get an array of words. It initializes a result string with "#". The first word from the array is converted to lowercase and appended to the result. Then, it iterates through the remaining words. For each word, it capitalizes the first letter and converts the rest of the letters to lowercase. This newly formatted word is then appended to the result string. The use of the + operator for string concatenation inside a loop is inefficient in Java. Each concatenation creates a new String object, copying the contents of the old string and the new part. This leads to poor performance, especially for long strings or many words. Finally, the resulting string is checked, and if its length exceeds 100, it's truncated to 100 characters.

1class Solution {2    public String generateTag(String caption) {3        String[] words = caption.trim().split("\\s+");4        if (words.length == 0 || words[0].isEmpty()) {5            return "#";6        }7 8        String tag = "#" + words[0].toLowerCase();9 10        for (int i = 1; i < words.length; i++) {11            String word = words[i];12            if (word.length() > 0) {13                tag += Character.toUpperCase(word.charAt(0));14                if (word.length() > 1) {15                    tag += word.substring(1).toLowerCase();16                }17            }18        }19 20        if (tag.length() > 100) {21            return tag.substring(0, 100);22        }23        return tag;24    }25}

Complexity

Time

`O(N^2)`, where `N` is the length of the caption. The `split` operation takes `O(N)`. The main bottleneck is the string concatenation in a loop. If the final tag has length `L` (where `L` is at most `N`), creating it via repeated concatenation can take `O(L^2)` time because strings are immutable in Java.

Space

`O(N^2)` in the worst case. The `words` array takes `O(N)` space. However, the repeated creation of new string objects during concatenation can lead to a high memory footprint from all the intermediate, discarded string objects.

Trade-offs

Pros

Simple to understand and implement.
Closely follows the logic described in the problem statement.

Cons

Highly inefficient due to repeated string object creation and copying.
Not recommended for performance-critical applications or large inputs.

This approach improves upon the brute-force method by using a StringBuilder to construct the final tag. StringBuilder is mutable and avoids the creation of multiple intermediate string objects, making the process much more efficient.

Algorithm

Trim and split the caption into an array of words.
Initialize a StringBuilder instance, sb, with "#".
Append the first word, converted to lowercase, to sb.
Iterate through the words array from the second word.
For each word, append its capitalized first letter to sb.
Append the rest of the word (from the second character), converted to lowercase, to sb.
After the loop, check the length of the StringBuilder.
If sb.length() > 100, return the substring of the first 100 characters.
Otherwise, convert the StringBuilder to a String and return it.

Walkthrough

Similar to the first approach, we start by splitting the caption into an array of words. Instead of a String, we use a StringBuilder initialized with "#". We process the first word by converting it to lowercase and appending it to the StringBuilder. We then loop through the rest of the words. For each word, we format it into camelCase (first letter uppercase, rest lowercase) and append it to the StringBuilder. Appending to a StringBuilder is an amortized constant-time operation (or proportional to the length of the appended string), which is much faster than string concatenation. After building the complete string in the StringBuilder, we convert it to a String. Finally, we truncate the string to 100 characters if its length is greater than 100.

1class Solution {2    public String generateTag(String caption) {3        String[] words = caption.trim().split("\\s+");4        if (words.length == 0 || words[0].isEmpty()) {5            return "#";6        }7 8        StringBuilder sb = new StringBuilder("#");9        sb.append(words[0].toLowerCase());10 11        for (int i = 1; i < words.length; i++) {12            String word = words[i];13            if (word.length() > 0) {14                sb.append(Character.toUpperCase(word.charAt(0)));15                if (word.length() > 1) {16                    sb.append(word.substring(1).toLowerCase());17                }18            }19        }20 21        if (sb.length() > 100) {22            return sb.substring(0, 100);23        }24        return sb.toString();25    }26}

Complexity

Time

`O(N)`, where `N` is the length of the caption. `split()` takes `O(N)`. Iterating through the words and appending to the `StringBuilder` takes time proportional to the total length of the words, which is `O(N)`. `toString()` also takes `O(N)`.

Space

`O(N)`. `O(N)` space is required for the `words` array and another `O(N)` for the `StringBuilder`'s internal buffer.

Trade-offs

Pros

Significantly more efficient than using string concatenation.
Standard and recommended way to build strings in Java.

Cons

Still requires an intermediate words array, which uses extra space.

This is the most optimal approach. It avoids splitting the string into an array altogether. Instead, it iterates through the caption character by character, building the final tag on the fly using a StringBuilder. This minimizes both time and space overhead.

Algorithm

Initialize a StringBuilder sb with "#".
Initialize a boolean flag capitalizeNext to false.
Iterate through each character c of the input caption.
If the length of sb reaches 100, stop processing and exit the loop.
If c is a space, set capitalizeNext to true (provided sb is not empty besides the initial '#') and continue to the next character.
If c is a letter: a. If capitalizeNext is true, append the uppercase version of c to sb and reset capitalizeNext to false. b. Otherwise, append the lowercase version of c to sb.
After the loop, convert sb to a string and return it.

Walkthrough

This optimal method avoids creating an intermediate array of words by processing the caption string in a single pass. It uses a StringBuilder for efficient string construction, initialized with "#". A boolean flag, capitalizeNext, tracks whether the next letter should be capitalized. This flag is set to true when a space is encountered (and at least one word has been added), indicating the start of a new word. The algorithm iterates through each character of the caption. If the character is a space, it updates the capitalizeNext flag and continues. If the character is a letter, it checks the capitalizeNext flag. If true, the letter is capitalized, appended to the StringBuilder, and the flag is reset to false. Otherwise, the letter is converted to lowercase and appended. This naturally handles the first word being all lowercase and subsequent words being camelCased. The loop also checks if the StringBuilder has reached the 100-character limit and breaks early to avoid extra work. This makes it highly efficient in terms of both time and space.

1class Solution {2    public String generateTag(String caption) {3        StringBuilder sb = new StringBuilder("#");4        boolean capitalizeNext = false;5        6        for (char c : caption.toCharArray()) {7            if (sb.length() == 100) {8                break;9            }10            11            if (c == ' ') {12                // Only set capitalize flag if we have already added some letters.13                // This handles leading spaces and multiple spaces between words.14                if (sb.length() > 1) {15                    capitalizeNext = true;16                }17            } else { // Character is a letter18                if (capitalizeNext) {19                    sb.append(Character.toUpperCase(c));20                    capitalizeNext = false;21                } else {22                    sb.append(Character.toLowerCase(c));23                }24            }25        }26        27        return sb.toString();28    }29}

Complexity

Time

`O(N)`, where `N` is the length of the caption. The algorithm iterates through the string only once.

Space

`O(L)`, where `L` is the length of the generated tag (at most 100). This is the space for the `StringBuilder`. This can be considered `O(min(N, 100))`, which is more efficient than the `O(N)` space required by the split-based approach.

Trade-offs

Pros

Most efficient in terms of both time and space.
Avoids creating intermediate data structures like an array of strings.
Processes the string in a single pass.

Cons

The logic can be slightly more complex to write correctly compared to the split-based approach.

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