In letter case permutation we have given a string consisting of alphabets and numbers only, each character in the string can be converted into lowercase and uppercase, find out all different strings which can be obtained from different combinations of lowercase and uppercase of each character in the string.
Table of Contents
Example
Input: str = “a1b2c3” Output: a1b2c3, A1b2c3, a1B2c3, a1b2C3, A1B2c3, a1B2C3, A1b2C3, A1B2C3 Input: str = “108” Output: 108 Input: str = “x” Output: x, X Input: str = “T2” Output: t2, T2
Types of Solution for letter case permutation
- Depth-first search based backtracking approach.
- Breadth first search based approach.
Depth first search based backtracking
Approach for letter case permutation
The idea is to generate each combination out of the given string in a depth-first manner.We implement a recursive code where we process each character of the input string from left to right (pos = 0 to pos = str.length()-1). If at a point during recursion, str[pos] is an alphabet, we add lowercase and uppercase of str[pos] to the resultant combination. However, if str[pos] is a digit, we simply add it as it is to the combination. The recursion gets terminated when the length of the resultant combination of the string becomes equal to the length of the input string.
Algorithm for letter case permutation
- Begin with an empty string (say s) and start processing string from left to right (pos = 0 to pos = input string length – 1).
- define base case: when string length becomes equal to original string length, print the string generated so far and terminate.
- if str[pos] is numeric, append str[pos] to s.
- Else if str[pos] is an alphabet, append lower case of str[pos] to a copy of s & also append upper case of str[pos] to a copy of s.
- once pos = input string length,i.e. end of the input string is reached, output the string generated so far and terminate the recursive function call.
The algorithm is depicted below:
Implementation
C++ Program
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void printPermutation(vector <char> str, int pos)
{
/* on reaching end of the string, print it and return */
if(pos == str.size())
{
for(auto i : str)
cout<<i;
cout<<endl;
return;
}
/* if string character is numeric ignore it and move on to next character */
if (str[pos] >= '0' && str[pos] <= '9')
{
printPermutation(str, pos + 1);
return;
}
/* if string character is alphabet
1. add the character in lowercase form
2. add the character in uppercase form
proceed to next character */
str[pos] = tolower(str[pos]);
printPermutation(str, pos + 1);
str[pos] = toupper(str[pos]);
printPermutation(str, pos + 1);
}
int main()
{
/* input string */
string input = "a1b2c3";
/* convert input string to vector of characters for processing */
vector <char> str(input.begin(),input.end());
printPermutation(str,0);
return 0;
}a1b2c3 a1b2C3 a1B2c3 a1B2C3 A1b2c3 A1b2C3 A1B2c3 A1B2C3
Java Program
import java.util.*;
import java.io.*;
class TutorialCup
{
static void printPermutation(char [] str, int pos)
{
/* on reaching end of the string, print it and return */
if(pos == str.length)
{
for(int i=0;i<pos;i++)
System.out.print(str[i]);
System.out.println();
return;
}
/* if string character is numeric ignore it and move on to next character */
if (str[pos] >= '0' && str[pos] <= '9')
{
printPermutation(str, pos + 1);
return;
}
/* if string character is alphabet
1. add the character in lowercase form
2. add the character in uppercase form
proceed to next character */
str[pos] = Character.toLowerCase(str[pos]);
printPermutation(str, pos + 1);
str[pos] = Character.toUpperCase(str[pos]);
printPermutation(str, pos + 1);
}
public static void main (String[] args)
{
/* input string */
String input = "a1b2c3";
/* convert input string to vector of characters for processing */
char [] str = input.toCharArray();
printPermutation(str,0);
}
}a1b2c3 a1b2C3 a1B2c3 a1B2C3 A1b2c3 A1b2C3 A1B2c3 A1B2C3
Complexity Analysis for letter case permutation
- T(n) = O(2n), n = length of the input string, we generate 2n combinations in the worst case when all the string characters are alphabets.
- A(n) = O(1).
Breadth first search
Approach for letter case permutation
The idea is to generate each combination out of the given string in a breadth-first manner. We implement an iterative code using a queue data structure where we process each character of the input string from left to right (pos = 0 to pos = str.length()-1). If at a point during iteration, str[pos] is an alphabet, we add lowercase and uppercase of str[pos] to the resultant combination. However, if str[pos] is a digit, we simply add it as it is to the combination. After the iteration is over, we output the contents of the queue.
Algorithm for letter case permutation
- Create a queue and insert an empty string into it along with pos = 0.
- Begin the BFS traversal.
- Pop a string and position index ( = pos) from the queue.
- to this string, append lowercase and uppercase of str[pos] if the str[pos] is a character.
- Add both the versions of the string obtained above into the queue.
- Else, if str[pos] is numeric, simply append the numeric to the string.
- Add the string to the queue.
- The traversal should go on till all the characters of the input string have been processed. i.e. pos = str.length()-1 .
- After the traversal is over, out all the strings from the queue.
The algorithm is depicted below:
It is evident from the algorithm above that, we need not append characters to strings, we simply change case of the alphabets moving from left to right.
Implementation
C++ Program
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void printPermutation(string str)
{
/* create queue to perform iterative traversal */
queue <pair<string,int>> q;
q.push({str,0});
/* begin iterative traversal */
while(!q.empty())
{
/* if we have strings which have been processed upto
the last index then terminate the loop */
if(q.front().second == str.size())
break;
string str = q.front().first;
int pos = q.front().second;
q.pop();
/* if character at index = pos is numeric
simply add it to the combination */
if(str[pos] >= '0' && str[pos] <= '9')
q.push({str,pos+1});
/* if character at index = pos is alphabet add
it's lowercase and uppercase to the combination */
else
{
/* insert string with character at index = pos as it is */
q.push({str,pos+1});
/* change the case of character at index = pos */
char ch = str[pos];
if(islower(ch))
str[pos] = str[pos] - 32;
else
str[pos] = str[pos] + 32;
/* insert string with character at index = pos after changing the case */
q.push({str,pos+1});
}
}
/* after iterative traversal is over print contents of the queue */
while(!q.empty())
{
cout<<q.front().first<<endl;
q.pop();
}
}
int main()
{
/* input string */
string input = "a1b2c3";
printPermutation(input);
return 0;
}a1b2c3 a1b2C3 a1B2c3 a1B2C3 A1b2c3 A1b2C3 A1B2c3 A1B2C3
Java Program
import java.util.*;
import java.io.*;
class TutorialCup
{
/* pair class is used to handle pair of
StringBuilder and Integer during traversal */
static class pair
{
StringBuilder s;
int index;
pair(StringBuilder sb,int pos)
{
s = new StringBuilder(sb);
index = pos;
}
}
static void printPermutation(StringBuilder s)
{
Queue <pair> q = new LinkedList<>();
q.add(new pair(s,0));
/* begin iterative traversal */
while(!q.isEmpty())
{
/* if we have strings which have been processed upto
the last index then terminate the loop */
if(q.peek().index == s.length())
break;
pair top = q.poll();
StringBuilder str = top.s;
int pos = top.index;
/* if character at index = pos is numeric
simply add it to the combination */
if(Character.isDigit(str.charAt(pos)))
q.add(new pair(str,pos+1));
/* if character at index = pos is alphabet add
it's lowercase and uppercase to the combination */
else
{
/* insert string with character at index = pos as it is */
q.add(new pair(str,pos+1));
/* change the case of character at index = pos */
char ch = str.charAt(pos);
if(Character.isLowerCase(ch))
str.setCharAt(pos,Character.toUpperCase(ch));
else
str.setCharAt(pos,Character.toLowerCase(ch));
/* insert string with character at index = pos after changing the case */
q.add(new pair(str,pos+1));
}
}
/* after iterative traversal is over print contents of the queue */
while(!q.isEmpty())
System.out.println(q.poll().s);
}
public static void main (String[] args)
{
/* input string */
String input = "a1b2c3";
/* convert input string to vector of characters for processing */
StringBuilder str = new StringBuilder(input);
printPermutation(str);
}
}a1b2c3 a1b2C3 a1B2c3 a1B2C3 A1b2c3 A1b2C3 A1B2c3 A1B2C3
Complexity Analysis for letter case permutation
- T(n) = O(2n), n = length of the input string, we generate 2n combinations in the worst case when all the string characters are alphabets.
- A(n) = O(2n), queue used to store all the string combinations.