 # Letter Case Permutation

## Letter Case Permutation

### Problem Statement

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

#### Examples:

Input: S = “r2q”

Output: [“r2q”, “R2q”, “r2Q”, “R2Q”].

Input: S = “678”

Output: [“678”]

Note:

1. S will be a string with length between 1 and 12.
2. S will consist only of letters or digits.

### Solution:

We don’t have to take care of digits as they can’t help to find more pernutations. We only have letters with us now. Suppose a string have L letters in it. The number of possible permutation will 2L.

This can be represented by bitmask bits.

For Example: we have g5h, we can represent all the possible permutations as g5h = 00, g5H = 01, G7h = 10, G7H = 11. Digits given in the input string are not included in bitmask.

According the possible bitmask, find out all the permutations, taking one bitmask at a time.

### Implementation

#### Java

```class Solution {
public List<String> letterCasePermutation(String S) {
int B = 0;
for (char c: S.toCharArray())
if (Character.isLetter(c))
B++;

List<String> ans = new ArrayList();

for (int bits = 0; bits < 1<<B; bits++) {
int b = 0;
StringBuilder word = new StringBuilder();
for (char letter: S.toCharArray()) {
if (Character.isLetter(letter)) {
if (((bits >> b++) & 1) == 1)
word.append(Character.toLowerCase(letter));
else
word.append(Character.toUpperCase(letter));
} else {
word.append(letter);
}
}

}

return ans;

}
}
```

#### Python

```class Solution(object):
def letterCasePermutation(self, S):
f = lambda x: (x.lower(), x.upper()) if x.isalpha() else x
return map("".join, itertools.product(*map(f, S)))
```

### Complexity Analysis

• Time Complexity: O(2n*n).
• Space Complexity: O(2n*n).
Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.