Letter case permutation

String Backtracking Bit Manipulation

75.7% acceptance

Feb 21, 2026

4831

161

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

/*
 * 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.
 * Example 1:
 * Input: s = "a1b2"
 * Output: ["a1b2","a1B2","A1b2","A1B2"]
 * Example 2:
 * Input: s = "3z4"
 * Output: ["3z4","3Z4"]
 * Constraints:
 * 1 <= s.length <= 12
 * s consists of lowercase English letters, uppercase English letters, and digits.
 */
impl Solution {
  pub fn letter_case_permutation(s: String) -> Vec<String> {
    let mut result = vec![];
    let chars: Vec<char> = s.chars().collect();
    fn backtrack(chars: &[char], idx: usize, current: &mut Vec<char>, result: &mut Vec<String>) {
      if idx == chars.len() {
        result.push(current.iter().collect());
        return;
      }
      current.push(chars[idx]);
      backtrack(chars, idx + 1, current, result);
      current.pop();
      if chars[idx].is_ascii_alphabetic() {
        let toggled = if chars[idx].is_uppercase() {
          chars[idx].to_ascii_lowercase()
        } else {
          chars[idx].to_ascii_uppercase()
        };
        current.push(toggled);
        backtrack(chars, idx + 1, current, result);
        current.pop();
      }
    }
    backtrack(&chars, 0, &mut vec![], &mut result);
    result
  }
}