LeetCode 3368 - First Letter Capitalization

This problem provides a database table named usercontent with two columns: | Column | Description | | --- | --- | | contentid | Unique identifier for each row | | contenttext | A text string containing words and spaces | The task is to produce a result table that contains: 1.

leetcodeharddatabase

LeetCode Problem 3368

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

This problem provides a database table named user_content with two columns:

Column Description
content_id Unique identifier for each row
content_text A text string containing words and spaces

The task is to produce a result table that contains:

  1. The original text
  2. A transformed version of the text where:
  • The first letter of every word is uppercase
  • Every other letter is lowercase
  • All spaces remain exactly as they originally appeared

In other words, we need to convert every word into title case while preserving spacing.

For example:

  • "hello world" becomes "Hello World"
  • "the QUICK brown fox" becomes "The Quick Brown Fox"
  • "TOP rated programming BOOKS" becomes "Top Rated Programming Books"

The important detail is that existing spaces must remain unchanged. If the original string contains multiple spaces between words, those spaces should still exist in the output exactly as they appeared.

The problem also guarantees that there are no special characters in the text. This simplifies processing because we only need to handle alphabetic characters and spaces.

Since this is a Database problem, the expected solution is SQL based. The main challenge is performing word-by-word capitalization directly inside SQL.

Important edge cases include:

  • Words already fully uppercase
  • Words already properly capitalized
  • Mixed-case words
  • Multiple consecutive spaces
  • Single-word strings
  • Empty strings, depending on database behavior

A naive implementation that simply uppercases the first character without lowercasing the rest would fail on inputs like "SQL" or "BOOKS" because the expected outputs are "Sql" and "Books".

Approaches

Brute Force Approach

The brute-force approach processes the string character by character.

The idea is to scan the text from left to right while tracking whether the current character starts a new word. A boolean flag such as new_word can indicate whether the next alphabetic character should be capitalized.

For each character:

  • If it is the beginning of a word, convert it to uppercase
  • Otherwise, convert it to lowercase
  • If the character is a space, preserve it and mark the next character as the start of a new word

This approach guarantees correctness because every character is explicitly examined and transformed according to its position inside the word.

However, implementing this directly in SQL is cumbersome and inefficient because SQL is not designed for low-level character iteration. Simulating character-by-character parsing often requires recursive queries, loops, or auxiliary tables.

Optimal Approach

The better approach uses built-in SQL string functions designed for text manipulation.

Most SQL dialects provide tools such as:

  • LOWER()
  • UPPER()
  • SUBSTRING()
  • Regular expression replacements

The key insight is that each word can be transformed independently:

  • Convert the entire string to lowercase
  • Capitalize the first character of each word

In MySQL 8+, regular expressions make this concise and efficient. We can:

  1. Convert the full string to lowercase
  2. Use a regex replacement to capitalize characters that:
  • Appear at the beginning of the string
  • Appear immediately after a space

This avoids manual iteration logic and produces clean SQL.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Character-by-character parsing
Optimal O(n) O(n) Uses SQL string and regex functions

Algorithm Walkthrough

Optimal Algorithm

  1. Start with the original content_text.

We preserve this value because the output requires both the original text and the transformed text. 2. Convert the entire string to lowercase.

This ensures that every non-leading character in a word becomes lowercase. Without this step, words like "BOOKS" would incorrectly remain uppercase. 3. Identify the first character of every word.

A character is considered the start of a word if:

  • It is at the beginning of the string
  • It follows a space
  1. Convert those starting characters to uppercase.

This creates proper title case formatting. 5. Preserve spaces exactly as they appear.

Since we only modify alphabetic characters, spacing remains unchanged automatically. 6. Return:

  • content_id
  • Original text as original_text
  • Transformed text as converted_text

Why it works

The algorithm works because every word is normalized into lowercase first, eliminating inconsistent capitalization. Then, only the first character of each word is promoted to uppercase. Since the transformation rule is applied consistently to every word boundary, the resulting text always satisfies the required title-case formatting.

Python Solution

Although this is fundamentally a SQL problem, the following Python implementation demonstrates the same logic algorithmically.

class Solution:
    def capitalizeTitle(self, content_text: str) -> str:
        result = []
        new_word = True

        for char in content_text:
            if char == ' ':
                result.append(char)
                new_word = True
            else:
                if new_word:
                    result.append(char.upper())
                    new_word = False
                else:
                    result.append(char.lower())

        return ''.join(result)

The implementation maintains a boolean flag named new_word.

Initially, the flag is set to True because the first character of the string starts a new word.

As the algorithm iterates through each character:

  • If the character is a space, it is copied directly into the result and the flag is reset.

  • If the character belongs to a word:

  • It is uppercased when starting a new word

  • Otherwise it is lowercased

The final list of characters is joined into the completed transformed string.

For the actual LeetCode Database submission, the SQL solution is:

SELECT
    content_id,
    content_text AS original_text,
    REGEXP_REPLACE(
        LOWER(content_text),
        '(^| )[a-z]',
        UPPER(SUBSTRING(REGEXP_SUBSTR(LOWER(content_text), '(^| )[a-z]'), -1))
    ) AS converted_text
FROM user_content;

Go Solution

package main

import (
	"strings"
	"unicode"
)

func capitalizeTitle(contentText string) string {
	var result strings.Builder
	newWord := true

	for _, ch := range contentText {
		if ch == ' ' {
			result.WriteRune(ch)
			newWord = true
		} else {
			if newWord {
				result.WriteRune(unicode.ToUpper(ch))
				newWord = false
			} else {
				result.WriteRune(unicode.ToLower(ch))
			}
		}
	}

	return result.String()
}

The Go implementation follows the same logic as the Python version.

A strings.Builder is used for efficient string construction because repeatedly concatenating immutable strings would be inefficient.

The unicode package handles uppercase and lowercase conversion safely for rune values.

Unlike Python strings, Go strings are UTF-8 encoded byte sequences, so iterating with range ensures proper rune handling.

Worked Examples

Example 1

Input:

"hello world of SQL"

Processing steps:

Character newWord Before Action Result
h True Uppercase H
e False Lowercase He
l False Lowercase Hel
l False Lowercase Hell
o False Lowercase Hello
space False Preserve space Hello
w True Uppercase Hello W
o False Lowercase Hello Wo
r False Lowercase Hello Wor
l False Lowercase Hello Worl
d False Lowercase Hello World

Final result:

"Hello World Of Sql"

Example 2

Input:

"the QUICK brown fox"

After lowercasing internally:

"the quick brown fox"

Capitalization process:

Word Converted
the The
quick Quick
brown Brown
fox Fox

Final result:

"The Quick Brown Fox"

Example 3

Input:

"data science AND machine learning"

Processing:

Original Word Lowercase Final
data data Data
science science Science
AND and And
machine machine Machine
learning learning Learning

Final result:

"Data Science And Machine Learning"

Example 4

Input:

"TOP rated programming BOOKS"

Processing:

Original Word Lowercase Final
TOP top Top
rated rated Rated
programming programming Programming
BOOKS books Books

Final result:

"Top Rated Programming Books"

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed once
Space O(n) Output string storage

The algorithm scans the input text exactly once from left to right. Every character undergoes at most one transformation operation, so the running time is linear in the size of the string.

The space complexity is also linear because a new output string must be constructed.

Test Cases

def capitalize_title(text: str) -> str:
    result = []
    new_word = True

    for char in text:
        if char == ' ':
            result.append(char)
            new_word = True
        else:
            if new_word:
                result.append(char.upper())
                new_word = False
            else:
                result.append(char.lower())

    return ''.join(result)

# Provided examples
assert capitalize_title("hello world of SQL") == "Hello World Of Sql"  # mixed lowercase and uppercase
assert capitalize_title("the QUICK brown fox") == "The Quick Brown Fox"  # uppercase normalization
assert capitalize_title("data science AND machine learning") == "Data Science And Machine Learning"  # mixed casing
assert capitalize_title("TOP rated programming BOOKS") == "Top Rated Programming Books"  # all caps handling

# Single word
assert capitalize_title("hello") == "Hello"  # single lowercase word

# Already formatted
assert capitalize_title("Hello World") == "Hello World"  # already correct formatting

# Multiple spaces
assert capitalize_title("hello   world") == "Hello   World"  # preserve consecutive spaces

# All uppercase
assert capitalize_title("SQL DATABASE SYSTEM") == "Sql Database System"  # normalize uppercase

# Empty string
assert capitalize_title("") == ""  # empty input

# Leading and trailing spaces
assert capitalize_title("  hello world  ") == "  Hello World  "  # preserve outer spaces
Test Why
"hello world of SQL" Validates normal mixed-case conversion
"the QUICK brown fox" Ensures uppercase letters become lowercase internally
"data science AND machine learning" Confirms every word is processed independently
"TOP rated programming BOOKS" Tests all-uppercase words
"hello" Validates single-word input
"Hello World" Confirms already-correct text remains correct
"hello world" Ensures multiple spaces are preserved
"SQL DATABASE SYSTEM" Tests full uppercase normalization
"" Validates empty-string handling
" hello world " Ensures leading and trailing spaces are preserved

Edge Cases

Multiple Consecutive Spaces

An implementation that splits the string using split() may accidentally collapse multiple spaces into a single space. For example:

"hello   world"

must remain:

"Hello   World"

The character-by-character approach avoids this problem because spaces are copied directly into the output without modification.

Fully Uppercase Words

Words like "BOOKS" or "SQL" can expose bugs in implementations that only capitalize the first letter without lowercasing the rest.

Incorrect output:

"BOOKS" -> "BOOKS"

Correct output:

"BOOKS" -> "Books"

The algorithm explicitly lowercases non-leading characters, ensuring proper normalization.

Leading and Trailing Spaces

Strings may contain spaces before or after the actual text:

"  hello world  "

A naive trimming approach would incorrectly remove those spaces.

The implementation preserves them because every character, including spaces, is copied exactly as encountered.