Interview Bootcamp
Vote

0% completed

​

String Permutations by changing case (medium)

Problem Statement

Given a string, find all of its permutations preserving the character sequence but changing case.

Example 1:

Input: "ad52"
Output: "ad52", "Ad52", "aD52", "AD52"

Example 2:

Input: "ab7c"
Output: "ab7c", "Ab7c", "aB7c", "AB7c", "ab7C", "Ab7C", "aB7C", "AB7C"

Constraints:

  • 1 <= str.length <= 12
  • str consists of lowercase English letters, uppercase English letters, and digits.

Try it yourself

Try solving this question here:

.....

.....

.....

Like the course? Get enrolled and start learning!
K

k

· 3 years ago

Given Approach:

#convert string to list of characters

chs = list(string) # if the current char is in upper case, change it to lower case or vice versa chs[i] = chs[i].swapcase() string = ''.join(chs))

Suggested Approach:

  • This will be much faster execution
  • Quick to wirte.

string = string[:j] + string[j].swapcase() + string[j+1:]

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findLetterCaseStringPermutations(self, text):
   
    def backtrack(word, result, seen, index):
      result.append(word[:])
      
      for i in range(index, len(word)): # loop through each character in the text
        char = word[i]
       
        if i not in seen and not char.isnumeric(): # if the character is not a number and have no been seen 
          seen.add(i)
          new_word = word[:i] + char.swapcase() + word[i + 1:]
          backtrack(new_word, result, seen, i) # recurse back 
        
          seen.remove(i)

    result = []
    backtrack(text, result, set(), 0)
    return result
Show 1 reply
A

Athanasios Petsas

· 5 years ago

In C++ sollution, we don't need to transform the string to an array of chars for doing the upper/lower case change and then transform it back to add it to the result vector; we can just do it in place. Here's the code having this change:

{code} static vector findLetterCaseStringPermutations(const string& str) { vector permutations; if (str == "") { return permutations; }

permutations.push_back(str); // process every character of the string one by one for (int i = 0; i < str.length(); i++) { if (!isalpha(str[i])) // only process characters, skip digits continue; // we'll take all existing permutations and change the letter case appropriately int n = permutations.size(); for (int j = 0; j < n; j++) { string newPerm = permutations[j]; // if the current char is in upper case change it to lo

T

Thai Minh

· 3 years ago

from collections import deque
class Solution:
  def findLetterCaseStringPermutations(self, str):
    permutations = []
    # TODO: Write your code here
    #[a,b,c]
    #[a][A]
    #[ab][aB][Ab][AB]
    #[abc][abC][aBc][aBC][Abc][AbC][ABc][ABC]
    # so loop through string, if char is number just append to all queue items
    # for char is number, append it with 2 cases: lowercase and uppercase
    curr_queue = deque()
    curr_queue.append("")
    for character in str:
      curr_queue_length = len(curr_queue)
      for _ in range(curr_queue_length):
        curr_str = curr_queue.popleft()
        if character.isdigit():
          curr_str += character
          if(len(curr_str) >= len(str)):
            permutations.append(curr_str)
          else:
            curr_queue.ap
T

Thai Minh

· 3 years ago

from collections import deque
class Solution:
  def findLetterCaseStringPermutations(self, str):
    permutations = []
    # TODO: Write your code here
    #[a,b,c]
    #[a][A]
    #[ab][aB][Ab][AB]
    #[abc][abC][aBc][aBC][Abc][AbC][ABc][ABC]
    # so loop through string, if char is number just append to all queue items
    # for char is number, append it with 2 cases: lowercase and uppercase
    curr_queue = deque()
    curr_queue.append("")
    for character in str:
      curr_queue_length = len(curr_queue)
      for _ in range(curr_queue_length):
        curr_str = curr_queue.popleft()
        if character.isdigit():
          curr_str += character
          if(len(curr_str) >= len(str)):
            permutations.append(curr_str)
          else:
            curr_queue.ap
Debasis B

Debasis B

· 2 years ago

    // List to store all permutations
    List<string> permutations = new List<string>();
    
    public List<string> findLetterCaseStringPermutations(string str)
    {
        // Begin the process
        find(currPermutation: str.ToCharArray(), index: 0);
        return permutations;
    }
    
    private void find(char[] currPermutation, int index)
    {
        // Base case: if index is out of bounds, add the current permutation to the list
        if (index == currPermutation.Length)
        {
            permutations.Add(string.Concat(currPermutation));
            return;
        }

        // If character is letter, toggle case and find next permutation 
        if (char.IsLetter(currPermutation[index]))
        {
            // Toggle case for the character at the
Viktor Pokazanyev

Viktor Pokazanyev

· 7 months ago

class Solution:
  def _permute(self, s, idx, cur_res, result):
    if idx == len(s):
      result.append(cur_res)
    else:
      if s[idx].isalpha():
        self._permute(s, idx + 1, cur_res + s[idx].swapcase(), result)
      self._permute(s, idx + 1, cur_res + s[idx], result)

  def findLetterCaseStringPermutations(self, str):
    permutations = []
    self._permute(str, 0, '', permutations)
    return permutations