Grokking the Coding Interview Patterns in Go/

...

/

Solution: Letter Case Permutation

Solution: Letter Case Permutation

Let’s solve the Letter Case Permutation problem using the Subsets pattern.

We'll cover the following...

Statement

Given a string, s, consisting of letters and digits, generate all possible variations by modifying each letter independently to be either lowercase or uppercase while keeping the digits unchanged. Each letter in the s string can appear in both cases across different variations, resulting in multiple possible combinations. Return a list containing all such variations in any order.

Constraints:

  • 1≤1 \leq s.length ≤12\leq12

  • s consists of lowercase English letters, uppercase English letters, and digits.

Solution

The solution follows the subsets pattern to generate all possible letter case permutations for s. The idea is to start with a result list containing an empty string. To build variations step by step, it iterates through s, processes each character, and updates the result list to store the variations of the current character. For each character in s: If it is a letter, create two permutations for each existing string in the result—one by appending the lowercase version and another by appending the uppercase version. Otherwise, if it is a digit, append it to each string in the result without any modifications. After processing all characters, the result contains all possible letter case combinations.

Now, let’s look at the solution steps in detail:

  1. We initialize a list, result, containing an empty string. This serves as the base case for building permutations.

  2. We iterate through each character, ch, of the s, and for each character:

    1. If ch is a letter:

      1. We Iterate through each string, str, in result, and to create permutations:

        1. We append the lowercase version of ch to str to create the first one.

        2. We append the uppercase version of ch to str to create the second one.

    2. If ch is a digit:

      1. We Iterate through each string, str, in result, and each iteration:

        1. We append the same digit to str to create the permutation.

  3. After iterating through all the characters in s, result contains all possible letter-case permutations.

Let’s look at the following illustration to get a better understanding of the solution:

Press + to interact
canvasAnimation-image
1 / 12

Let’s look at the code for the solution we just discussed.

package main
import (
	"fmt"
	"strings"
	"unicode"
)
func letterCasePermutation(s string) []string {
	result := []string{""} 
	for _, ch := range s {
		size := len(result) 
		for i := 0; i < size; i++ {
			str := result[i]
			if unicode.IsLetter(ch) {
				result[i] = str + string(unicode.ToLower(ch))
				result = append(result, str+string(unicode.ToUpper(ch)))
			} else {
				result[i] = str + string(ch)
			}
		}
	}
	return result
}
// Driver function
func main() {
	stringsList := []string{"a1b2", "3z4", "ABC", "123", "xYz"} 
	for i, s := range stringsList {
		fmt.Printf("%d.\ts: \"%s\"\n", i+1, s)
		output := letterCasePermutation(s)
		fmt.Print("\n\tOutput: [")
		for j, val := range output {
			fmt.Printf("\"%s\"", val)
			if j < len(output)-1 {
				fmt.Print(", ")
			}
		}
		fmt.Println("]\n" + strings.Repeat("-", 100)) 
	}
}
Letter Case Permutation

Time complexity

The time complexity of the solution is ...