2

I'm trying to generate all capital permutations of a string.

For example:

capitalPermutations(word) - Given a string of letters, return all the possible combinations of lower and uppercase letters of that word.

Example: 'abc'

Ouput: ['abc' 'Abc' 'aBc' 'ABc' 'abC' 'AbC' 'aBC' 'ABC']

Implement this in both iterative and recursive way.

This is my attempt:

function capitalPermutations(word) {
  const res = new Set();
  
  // Push the actual word first.
  res.add(word);
  
  helper(word, res, '');
  
  return res;
  
  function helper(word, res, str='') {
    
    if(str.length === word.length) return;
    
    const len = word.length;
    res.add(word);
    
    // Capitalization
    for(let i=0; i< word.length; i++) {
      const substr = word.substring(0, i+1); // a, ab, abc
      str += substr; // str === "ABC" | len = 3
      const upper = str.toUpperCase(); // A, AB, ABC
      const remaining = `${upper}${word.substring(i, len)}`; // Abc , ABc, 
      helper(remaining, res, str);
    }
  }

}
var testWord1 = "abc"
console.log(capitalPermutations(testWord1))

Issue: It's going into infinite recursion. Even though I have a breaking condition. Would really appreciate if someone can correct where I'm going wrong.

Improve this question
6
  • @kmgt There's nothing wrong with it, that's what recursion is actually good for - it's not easily achievable with iteration. Commented Sep 5, 2019 at 20:58
  • The assignment is confusing. This actually has nothing to do with permutations, which are about ordering. Commented Sep 5, 2019 at 20:59
  • "I would really appreciate if someone can correct where I'm going wrong" - could you please try to explain where you're going at all? I don't get your approach at all. Why are you iterating over the word length, and getting all prefixes from it? Why do you do str += substr? In your base case, did you mean to compare to the original words length (the one passed to capitalPermutations), or to the word that's getting passed in the recursive call? And why do you add the word to the result in each recursion step, not only once at the end? Commented Sep 5, 2019 at 21:06
  • @Bergi thanks for the comment. I used str to just keep track of how many strings I'm processing. I understand my code is confusing (just trying to learn!) appreciate your help and all your comments. In my base case, I was hoping to compare to my original word length (not the one that's getting passed) my bad! Commented Sep 5, 2019 at 21:11
  • 1
    Wouldn't generating all permutations produce strings such as cab, bac, etc.? Isn't this assignment only about generating all the different variations of casing? Commented Sep 6, 2019 at 7:23

4 Answers 4

Reset to default
2

Traverse the string like a binary tree

const permute = (str, prefix='') => {
  const idx = prefix.length
  if (idx===str.length)
    return [prefix]

  const lower = str[idx].toLowerCase()
  const upper = str[idx].toUpperCase()

  return [...permute(str, prefix + lower), ...permute(str, prefix + upper)]
}

console.log(permute('abc'))

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

You could take a recursive function which takes the collected letters of the last visited indices and check if the collected letter string has the same length as the given string. Then push the string to the result set.

The key is a double call of the recursion with a lower case letter and an upper case letter.

function capitalPermutations(word) {
    function iter(temp = '') {
        if (temp.length === word.length) {
            result.push(temp);
            return;
        }
        iter(temp + word[temp.length].toLowerCase());
        iter(temp + word[temp.length].toUpperCase());
    }

    var result = [];
    iter();
    return result;
}

console.log(capitalPermutations('abc'));

The same with an iterative approach

function capitalPermutations(word) {
    var result = [''],
        temp,
        i, j, upper, lower;

    for (i = 0; i < word.length; i++) {
        temp = result;
        result = [];
        lower = word[i].toLowerCase();
        upper = word[i].toUpperCase();
        for (j = 0; j < temp.length; j++) {
            result.push(temp[j] + lower, temp[j] + upper);
        }
    }
    return result;
}

console.log(capitalPermutations('abc'));

Improve this answer

6 Comments

thank you. Soo clean! If I were to do this iteratively, how would I do it? I'm thinking of having two for Loops and doing substring in one of the loop?
This also works with "abcde", so it seems to be a good solution.
^^ This is the reason why I love SO so much!
@TechnoCorner. for the iterative approach, you need two loops, one for the characters of the word and one for the part result. please see edit.
@customcommander it's a typo..let me fix the question. This is the right answer
|
2

Here's one with flatMap:

function f(str){
  return str ? f(str.slice(1)).flatMap(sfx =>
    [str[0].toLowerCase() + sfx, str[0].toUpperCase() + sfx]) : [""]
}

console.log(JSON.stringify(f("abc")))

Improve this answer

Comments

1

Iterative:

function f(str){
  let res = [""]
  for (let c of str)
    res = res.flatMap(pfx =>
      [pfx + c.toUpperCase(), pfx + c.toLowerCase()])
  return res
}

console.log(JSON.stringify(f("abc")))

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.