Permutations of given string

A decade ago I was asked to find all possible permutations of a given string in a software company interview . There were plenty of solutions available in various other blogs but nothing was perfect and I felt that something could be improved in those existing algorithms . Although I was not able to give the right answer in the interview but I want to share my thoughts on how to solve this complex problem in a unique manner. The question was tough and it requires lot of thought process to write the code for this given problem . Thank you for testing my IQ again and again .

That's why I have written my own non recursive as well as recursive algorithm to solve this complex problem . I hope the solution is very clear and my algorithm is different and it does not do any swap operations because it is not a sorting problem and neither my algorithm converts string to array which can be done with StringBuilder() in Java or String split() in Javascript . It also handles strings with duplicate characters .

/*

   Find permutations of a given string in recursive way original source code written by me 
   copyright information
   Author Name - Raj Gopal Bhallamudi
   Email - flame527@yahoo.com , rajgopal527@gmail.com
   Facebook - facebook.com/r5274
   Instagram - instagram.com/bhrajgopal
   Date - 26th June 2025

   */



let startsWith=[];


function permutationRecursive(start) {

    let newString, newRemainingString , length=start.length;

    for(let counter = 0; counter < length; counter++) {
        newString = start.charAt(counter);
        newRemainingString = start.substring(0, counter)+start.substring(counter + 1, length);
        if(startsWith.indexOf(newString) === -1) {
            permutationSubString(newString, newRemainingString);
            startsWith.push(newString);
        }

    }

}

function  permutationSubString(start, remainingString) {

    let newString, newRemainingString , length=remainingString.length;

    if(remainingString===""){
        console.log(start);
        return
    }

    for(let counter = 0; counter < length; counter++) {
        newString = start + remainingString.charAt(counter);
        newRemainingString = remainingString.substring(0, counter)+remainingString.substring(counter + 1, length);
        if(startsWith.indexOf(newString) === -1) {
            permutationSubString(newString, newRemainingString);
            if(newRemainingString!=="")
                startsWith.push(newString);
        }

    }



}

permutationRecursive("XYZ");



/*


    Author Name - Unknown 

   */


let startsWith=[];

function permutationRecursive(start, remainingString) {

    let newString, newRemainingString , length=remainingString.length;

    if(remainingString.length === 0 ) {
       console.log(start);
       return;
    }

    for(let counter = 0; counter < length; counter++) {
        newString = start + remainingString.charAt(counter);
        newRemainingString = remainingString.substring(0, counter)+remainingString.substring(counter + 1, length);
        if(startsWith.indexOf(newString) === -1) {
            permutationRecursive(newString, newRemainingString);
            if(newRemainingString.length!==0)
                startsWith.push(newString);
        }

    }


}

permutationRecursive("","XYZ")



/*
    Toughest Programming  Challenge
    Find permutations of a given string in non  recursive way including duplicate characters 
    copyright information
    Author Name - Raj Gopal Bhallamudi
    Email - flame527@yahoo.com , rajgopal527@gmail.com
    Facebook - facebook.com/r5274
    Instagram - instagram.com/bhrajgopal
    Date - 26th June 2025

 */

const startsWith = [];
const stack = [];
let result = ""

function permutationNonRecursive(start) {

    let firstChar,newString, newRemainingString, stringLength = start.length, length;

    for (let counter = 0; counter < stringLength; counter++) {

        firstChar = newString = start.charAt(counter);
        newRemainingString = start.substring(0, counter) + start.substring(counter + 1, stringLength);

        if (startsWith.indexOf(newString) === -1) {

            stack.unshift({newString, newRemainingString});
            while (stack.length > 0) {
                let {newString: start, newRemainingString: remainingString} = stack.shift();
                length = remainingString.length;
                    for (let innerCounter = 0; innerCounter < length; innerCounter++) {
                        newString = start + remainingString.charAt(innerCounter);
                        newRemainingString = remainingString.substring(0, innerCounter) +
                                                  remainingString.substring(innerCounter + 1, length);
                            if (newRemainingString.length === 0) {
                               result = result + newString + " ";
                               } else {
                            if (startsWith.indexOf(newString) === -1){
                                stack.unshift({newString, newRemainingString});
                                startsWith.push(newString);
                            }
                        }
                    }
            }
            startsWith.push(firstChar);
        }
    }

}


let string = "XYZ";

permutationNonRecursive(string);
console.log(result);