# Letter Case Permutation

Posted: 11 Mar, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### Note:

``````1. You can print the array in any order.

2. The string 'S' only contains English alphabets and digits.
``````
##### Input Format:
``````The first line contains an integer T, which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first and only line of each test case contains a string 'S', as described in the problem statement.
``````
##### Output Format:
``````For each test case, print a single line containing space-separated strings denoting all possible strings by transforming, as described in the problem statement.

The output for each test case will be printed in a separate line.
``````
##### Note:
``````You do not need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 100
1 <= |S| <= 12

Where |S| denotes the length of string 'S'.

Time Limit: 1 sec.
`````` Approach 1

The idea here is to use the recursion. For each index i, where 0 <= i < |S|, if S[i] is a digit, then there is only one option available, which is to call the function again with i + 1, and if S[i] is a letter, then there are two options available. The first one is to change S[i] to the lowercase (if already is in the lowercase, then doesn’t matter) and call the function again with i + 1. The second one is to change S[i] to the uppercase (if already is in the uppercase, then doesn’t matter) and call the function again with i + 1.

When i becomes equal to the length of the string S, then just add the string S to the answer array and which is also the base condition for the recursion function. So, we can say that for each index, if it a letter, then two options are available, which may go up to 2 ^ N (in the worst case), where N is the length of the string.

Steps:

• Create an empty array ans of strings to store all the strings.
• Call the function stringPer(S, ind, ans), where ind is the starting index which is 0, S is the input string, and ans is the array to store the strings.
• Return the array ans.

void stringPer(string S, int ind, int ans[]) :

• If ind == S.size(), then add the string S to the ans and return.
• If S[ind] is a digit, then call the function stringPer(S, ind + 1, ans).
• Else, call the function two times as follows:
• Convert S[ind] to lower case, and then call stringPer(S, ind + 1, ans).
• Convert S[ind] to upper case, and then call stringPer(S, ind + 1, ans).