LeetCode 1667 - Fix Names in a Table

LeetCode Problem 1667

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

This problem provides a database table named Users with two columns: user_id and name. The user_id column uniquely identifies each user, while the name column stores a person's name using a mixture of uppercase and lowercase English letters.

The task is to normalize every name so that it follows standard capitalization rules:

• The first character must be uppercase
• Every remaining character must be lowercase

For example:

• "aLice" becomes "Alice"
• "bOB" becomes "Bob"
• "JOHN" becomes "John"

The query must return two columns:

• user_id
• the corrected name

The output must also be sorted in ascending order by user_id.

The input guarantees that names contain only alphabetic characters. This simplifies the problem because we do not need to handle spaces, punctuation, numbers, or special symbols.

Since this is a database problem, the primary challenge is understanding which SQL string functions can transform the name correctly. A naive implementation might only uppercase the first character and forget to lowercase the remaining characters, which would produce incorrect results such as "ALICE" becoming "ALICE" instead of "Alice".

Another possible mistake is mishandling very short names, especially names with only one character. The solution must still work correctly in that case.

Approaches

Brute Force Approach

A brute force style solution would manually process each character of every name. The query could:

1. Extract the first character
2. Convert it to uppercase
3. Iterate through every remaining character
4. Convert each remaining character to lowercase
5. Concatenate all characters back together

This approach is logically correct because it explicitly rebuilds the string character by character in the desired format.

However, this solution is unnecessarily complicated for SQL. Database systems already provide optimized built in string functions that can perform substring extraction and case conversion efficiently. Writing character by character logic would make the query harder to read, maintain, and optimize.

Optimal Approach

The key observation is that we only need two transformations:

• Convert the first character to uppercase
• Convert the rest of the string to lowercase

SQL provides exactly the functions needed for this:

• UPPER() converts text to uppercase
• LOWER() converts text to lowercase
• SUBSTRING() extracts parts of the string
• CONCAT() joins strings together

Using these functions, we can construct the corrected name directly:

1. Extract the first character and uppercase it
2. Extract the remaining substring and lowercase it
3. Concatenate the two parts together

This produces a clean and efficient solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Processes every character manually
Optimal	O(n)	O(n)	Uses built in SQL string functions efficiently

Here, n represents the total number of characters processed across all names.

Algorithm Walkthrough

1. Read each row from the Users table.

Each row contains a user_id and a name value that may have inconsistent capitalization. 2. Extract the first character of the name.

We use SUBSTRING(name, 1, 1) to obtain the first letter. This is the character that must become uppercase. 3. Convert the first character to uppercase.

Applying UPPER() ensures the first character follows the required formatting rule. 4. Extract the remaining part of the name.

We use SUBSTRING(name, 2) to obtain all characters starting from index 2. 5. Convert the remaining substring to lowercase.

Applying LOWER() ensures all trailing characters are lowercase, even if the original string contained uppercase letters. 6. Concatenate the two transformed parts.

CONCAT() joins the uppercase first character with the lowercase remainder. 7. Return the formatted result ordered by user_id.

The problem explicitly requires sorting the output table by user_id.

Why it works

The algorithm works because every valid output name must satisfy exactly two conditions:

• The first character is uppercase
• Every subsequent character is lowercase

The solution constructs the output string directly according to these rules. Since every character belongs either to the first position or the remaining positions, every letter is transformed correctly.

Python Solution

Although this is a SQL problem on LeetCode, the equivalent Python logic is shown below to illustrate the transformation process clearly.

class Solution:
    def fixName(self, name: str) -> str:
        if not name:
            return ""

        return name[0].upper() + name[1:].lower()

Implementation Explanation

The implementation first checks whether the string is empty. While the SQL problem guarantees valid names, defensive programming makes the function more robust.

The expression name[0].upper() converts the first character to uppercase.

The expression name[1:].lower() extracts all remaining characters and converts them to lowercase.

Finally, the two pieces are concatenated together to form the corrected name.

For the actual LeetCode database submission, the SQL query is the required answer:

SELECT
    user_id,
    CONCAT(
        UPPER(SUBSTRING(name, 1, 1)),
        LOWER(SUBSTRING(name, 2))
    ) AS name
FROM Users
ORDER BY user_id;

Go Solution

The equivalent Go implementation is shown below for completeness.

package main

import (
	"strings"
)

func fixName(name string) string {
	if len(name) == 0 {
		return ""
	}

	first := strings.ToUpper(name[:1])
	rest := strings.ToLower(name[1:])

	return first + rest
}

Go Specific Notes

Go strings are immutable, similar to Python strings, so the solution constructs a new string instead of modifying the original.

The strings.ToUpper() and strings.ToLower() functions handle case conversion cleanly.

The slicing syntax differs slightly from Python, but the logic remains identical.

Worked Examples

Example 1

Input table:

user_id	name
1	aLice
2	bOB

Processing Row 1

Original name: "aLice"

Step	Value
First character	"a"
Uppercase first character	"A"
Remaining substring	"Lice"
Lowercase remaining substring	"lice"
Final result	"Alice"

Processing Row 2

Original name: "bOB"

Step	Value
First character	"b"
Uppercase first character	"B"
Remaining substring	"OB"
Lowercase remaining substring	"ob"
Final result	"Bob"

Final output:

user_id	name
1	Alice
2	Bob

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every character in every name is processed once
Space	O(n)	New transformed strings are created

The algorithm performs a constant number of operations per character. Since each character participates in either the uppercase or lowercase transformation exactly once, the total runtime scales linearly with the total amount of input text.

The space complexity is also linear because the transformed strings require additional storage.

Test Cases

def fix_name(name: str) -> str:
    if not name:
        return ""
    return name[0].upper() + name[1:].lower()

assert fix_name("aLice") == "Alice"      # mixed casing
assert fix_name("bOB") == "Bob"          # uppercase tail
assert fix_name("ALICE") == "Alice"      # fully uppercase
assert fix_name("alice") == "Alice"      # fully lowercase
assert fix_name("A") == "A"              # single uppercase character
assert fix_name("z") == "Z"              # single lowercase character
assert fix_name("JoHn") == "John"        # alternating case
assert fix_name("") == ""                # empty string edge case
assert fix_name("mARY") == "Mary"        # common mixed case input
assert fix_name("xYz") == "Xyz"          # short mixed case input

Test	Why
"aLice"	Validates standard mixed case conversion
"bOB"	Ensures uppercase trailing letters become lowercase
"ALICE"	Confirms fully uppercase names normalize correctly
"alice"	Confirms lowercase names gain uppercase first letter
"A"	Tests single character uppercase input
"z"	Tests single character lowercase input
"JoHn"	Verifies alternating capitalization handling
""	Tests defensive empty string handling
"mARY"	Ensures proper formatting of common mixed patterns
"xYz"	Tests short strings with inconsistent casing

Edge Cases

Single Character Names

A name containing only one character can easily cause substring bugs. For example, accessing characters after index 1 could fail in some implementations.

This solution handles the case correctly because the substring after the first character simply becomes an empty string. Concatenating the uppercase first character with an empty string still produces the correct result.

Fully Uppercase Names

Inputs like "ALICE" are important because a naive solution might only uppercase the first character and leave the remaining letters unchanged.

The implementation explicitly lowercases the remaining substring, ensuring "ALICE" becomes "Alice".

Fully Lowercase Names

Inputs like "alice" verify that the algorithm correctly capitalizes the first letter while preserving lowercase formatting for the rest of the string.

The solution converts the first character independently and lowercases the suffix, producing "Alice" correctly.

Empty Strings

Although the database constraints guarantee valid names, defensive implementations should still consider empty strings.

The Python and Go examples explicitly check for empty input and return an empty string safely instead of causing index access errors.