Generate Tag for Video Caption
EasyPrompt
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 <= 150captionconsists 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
captionand split it into an array ofwordsusing one or more spaces as a delimiter. - Handle the edge case of an empty caption, returning
"#"if no words are found. - Initialize a
Stringvariabletagwith"#"followed by the first word converted to lowercase. - Iterate through the
wordsarray 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
tagstring using the+=operator. - After the loop, if the length of
tagis 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.
class Solution { public String generateTag(String caption) { String[] words = caption.trim().split("\\s+"); if (words.length == 0 || words[0].isEmpty()) { return "#"; } String tag = "#" + words[0].toLowerCase(); for (int i = 1; i < words.length; i++) { String word = words[i]; if (word.length() > 0) { tag += Character.toUpperCase(word.charAt(0)); if (word.length() > 1) { tag += word.substring(1).toLowerCase(); } } } if (tag.length() > 100) { return tag.substring(0, 100); } return tag; }}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.
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.