# Generate Tag for Video Caption
**Difficulty:** EASY
[External](https://leetcode.com/problems/generate-tag-for-video-caption)
Canonical: https://scaleengineer.com/dsa/problems/generate-tag-for-video-caption
**Data structures:** String
---
## Problem
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:

1. **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.
2. **Remove** all characters that are not an English letter, **except** the first `'#'`.
3. **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
## Brute Force using String Concatenation
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.
**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.
**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.
### Explanation
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.
```java
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;
    }
}
```
### 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`.

## Optimized String Building with StringBuilder
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.
**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.
**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.
### Explanation
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.
```java
class Solution {
    public String generateTag(String caption) {
        String[] words = caption.trim().split("\\s+");
        if (words.length == 0 || words[0].isEmpty()) {
            return "#";
        }

        StringBuilder sb = new StringBuilder("#");
        sb.append(words[0].toLowerCase());

        for (int i = 1; i < words.length; i++) {
            String word = words[i];
            if (word.length() > 0) {
                sb.append(Character.toUpperCase(word.charAt(0)));
                if (word.length() > 1) {
                    sb.append(word.substring(1).toLowerCase());
                }
            }
        }

        if (sb.length() > 100) {
            return sb.substring(0, 100);
        }
        return sb.toString();
    }
}
```
### 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.

## Most Efficient Single-Pass Approach
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.
**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.
**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.
### Explanation
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.
```java
class Solution {
    public String generateTag(String caption) {
        StringBuilder sb = new StringBuilder("#");
        boolean capitalizeNext = false;
        
        for (char c : caption.toCharArray()) {
            if (sb.length() == 100) {
                break;
            }
            
            if (c == ' ') {
                // Only set capitalize flag if we have already added some letters.
                // This handles leading spaces and multiple spaces between words.
                if (sb.length() > 1) {
                    capitalizeNext = true;
                }
            } else { // Character is a letter
                if (capitalizeNext) {
                    sb.append(Character.toUpperCase(c));
                    capitalizeNext = false;
                } else {
                    sb.append(Character.toLowerCase(c));
                }
            }
        }
        
        return sb.toString();
    }
}
```
### 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.