Letter Case Permutation - Practice Coding Problems

Letter Case Permutation - Problem

Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. Return the output in any order.

Note: Only alphabetic characters can be transformed - digits and special characters remain unchanged.

Input & Output

Example 1 — Basic Case

$ Input: s = "a1b2"

› Output: ["a1b2","a1B2","A1b2","A1B2"]

💡 Note: Two letters 'a' and 'b' can each be upper or lower case. 2×2 = 4 combinations total.

Example 2 — Single Character

$ Input: s = "3z4"

› Output: ["3z4","3Z4"]

💡 Note: Only one letter 'z', so 2 possibilities: lowercase 'z' or uppercase 'Z'.

Example 3 — No Letters

$ Input: s = "12345"

› Output: ["12345"]

💡 Note: No letters to transform, so only one result: the original string.

Constraints

1 ≤ s.length ≤ 12
s consists of lowercase English letters, uppercase English letters, and digits

Visualization

Tap to expand

Understanding the Visualization

Input

String "a1b2" with mixed letters and digits

Transform

Each letter can be upper or lower case

Output

All possible case combinations

Key Takeaway

🎯 Key Insight: Each letter doubles the total combinations, creating 2^n permutations

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that each letter has exactly 2 states (upper/lower), creating 2^n total combinations. Best approach uses backtracking or bit manipulation to systematically generate all permutations. Time: O(2^n × n), Space: O(2^n × n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Combinations	O(2^n × n)	O(2^n × n)	Try all 2^n possible combinations of uppercase/lowercase letters
Bit Manipulation	O(2^n × m)	O(2^n × m)	Use bitmask to represent all possible upper/lowercase combinations

Brute Force - Generate All Combinations — Algorithm Steps

Iterate through each character
If letter, try both cases recursively
If digit, keep as is and continue
Collect all valid combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with empty string, process each character

Branch

For each letter, create two branches (upper/lower)

Collect

When string is complete, add to result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

void backtrack(const char* s, int index, char* current, int pos, char result[][100], int* count) {
    if (index == strlen(s)) {
        current[pos] = '\0';
        strcpy(result[*count], current);
        (*count)++;
        return;
    }
    
    char ch = s[index];
    if (isalpha(ch)) {
        // Try lowercase
        current[pos] = tolower(ch);
        backtrack(s, index + 1, current, pos + 1, result, count);
        // Try uppercase
        current[pos] = toupper(ch);
        backtrack(s, index + 1, current, pos + 1, result, count);
    } else {
        // Keep digits/special chars as is
        current[pos] = ch;
        backtrack(s, index + 1, current, pos + 1, result, count);
    }
}

int main() {
    char s[100];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char result[1000][100];
    char current[100];
    int count = 0;
    
    backtrack(s, 0, current, 0, result, &count);
    
    printf("[");
    for (int i = 0; i < count; i++) {
        printf("\"%s\"", result[i]);
        if (i < count - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n × n)

2^n combinations, each taking O(n) time to build the string

⚠ Quadratic Growth

Space Complexity

O(2^n × n)

Storing 2^n strings, each of length n, plus recursion stack depth n

⚠ Quadratic Space

185.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler