Generate Tag for Video Caption

Difficulty: Easy | Acceptance: 32.50% | Paid: No Topics: String, Simulation

You are given a string caption representing the caption of a video. Your task is to generate a tag for the video based on the following rules:

1. The tag must start with the character #.
2. The tag must consist of the first character of each word in the caption.
3. The first character of the tag (immediately following #) must be uppercase.
4. All other characters in the tag must be lowercase.
5. If the caption is empty or contains only spaces, return #.

Words are considered to be separated by spaces.

• Examples
• Constraints
• Approach 1: Split and Build
• Approach 2: Single Pass Iteration

Examples

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

0 <= caption.length <= 1000
caption consists of printable ASCII characters.

Approach 1: Split and Build

Intuition We can split the input string into an array of words using spaces as delimiters. Then, we iterate through these words, extracting the first character of each. We apply the capitalization rules (uppercase for the very first character, lowercase for the rest) and join them back together with a # prefix.

Steps

• Split the caption string by whitespace to get a list of words.
• If the list is empty (or only contains empty strings), return #.
• Initialize a result string with #.
• Iterate through the words:
  • If it is the first word, append the uppercase version of its first character.
  • Otherwise, append the lowercase version of its first character.
• Return the constructed string.

class Solution:
    def generateTag(self, caption: str) -> str:
        # Split by whitespace, which handles multiple spaces automatically
        words = caption.split()
        
        if not words:
            return "#"
        
        tag = ["#"]
        for i, word in enumerate(words):
            if word:
                first_char = word[0]
                if i == 0:
                    tag.append(first_char.upper())
                else:
                    tag.append(first_char.lower())
                    
        return "".join(tag)

Complexity

• Time: O(N), where N is the length of the string. Splitting and iterating are linear operations.
• Space: O(N) to store the array of words and the resulting string.
• Notes: This approach is very readable and leverages built-in string manipulation functions effectively.

Approach 2: Single Pass Iteration

Intuition Instead of creating an intermediate array of words, we can iterate through the string once. We identify the start of a word by checking if the current character is not a space and the previous character is a space (or it is the start of the string). This allows us to build the tag on the fly with O(1) extra space (excluding the output).

Steps

• Initialize a result string with #.
• Initialize a boolean flag firstWordFound to false.
• Iterate through the string with an index i:
  • If caption[i] is not a space:
    • Check if it is the start of a word (i == 0 or caption[i-1] is a space).
    • If it is the start of a word:
      • If firstWordFound is false, append the uppercase version of caption[i] and set firstWordFound to true.
      • Otherwise, append the lowercase version of caption[i].
• Return the result.

class Solution:
    def generateTag(self, caption: str) -> str:
        res = ["#"]
        first_word_found = False
        n = len(caption)
        
        for i in range(n):
            char = caption[i]
            # Check if current char is not space and (is start of string or prev char is space)
            if char != ' ' and (i == 0 or caption[i-1] == ' '):
                if not first_word_found:
                    res.append(char.upper())
                    first_word_found = True
                else:
                    res.append(char.lower())
                    
        return "".join(res)

Complexity

• Time: O(N), where N is the length of the string. We traverse the string exactly once.
• Space: O(1) auxiliary space (excluding the space required for the output string).
• Notes: This approach is more memory efficient as it avoids storing the split array, though it is slightly more verbose.