How to scramble a word, keeping first and last characters the same?

Question

I have a task, which is to scramble a single word, whose size is greater than 3 letters.

The scrambled word must not be equal to the original, and the first and last letters of the word must remain the same.

For example, the word stack, could give the one of the following results:

• satck
• scatk
• stcak
• sactk
• etc

While words like is or hey for example, would remain unchanged for being too small.

My attempt to do this can be seen below. I have a JavaScript function that received a word to scramble, and then I choose random indexes within a certain limit to create a new scrambled word and return it. If the index I have chosen was already picked, then I try again hoping for a new result.

/**
 * Returns a scrambled word with the first and last letters unchanged
 * that is NOT EQUAL to the given parameter 'word', provided it has 
 * more than three characters.
 */
function scrambleWord(word){

  if(word.length <= 3)
    return word;

  var selectedIndexes, randomCharIndex, scrambledWord = word;

  while(word === scrambledWord){
    selectedIndexes = [], randomCharIndex, scrambledWord = '';
    scrambledWord += word[0];
    for(var j = 0; j < word.length-2; j++){

      //select random char index making sure it is not repeated
      randomCharIndex = getRandomInt(1, word.length-2);
      while(selectedIndexes.indexOf(randomCharIndex) > -1 && selectedIndexes.length != word.length-2){
        randomCharIndex = getRandomInt(1, word.length-2);
      }

      scrambledWord += word[randomCharIndex];
      selectedIndexes.push(randomCharIndex);
    }
    scrambledWord += word[word.length-1];
  }
  return scrambledWord;
}

/**
 * Returns a random integer between min (inclusive) and max (inclusive)
 * Using Math.round() will give you a non-uniform distribution!
 * See: http://stackoverflow.com/a/1527820/1337392
 */
function getRandomInt(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

The problem with this approach, is that it is too slow. I fail the tests because I exceed the time limit of 6 seconds, so I definitely need to improve this solution, but I can't see where I can do it.

From an algorithm perspective, what is the most efficient way that uses the least amount of worst case operations that I can approach this problem?

Answer 1

Something along the following lines; treating the string as a character array:

• Handle strings that are 3 or fewer characters, or all the middle characters are the same
• Create a sublist of the letters excluding the first and last
• Fisher-Yates shuffle the middle letters until they don't match the original (this can be done in O(n) time)
• Reattach the first and last letter

A faster shuffle can be used, if it is allowed to be less random (e.g. ln(n) random swaps). In the extreme case this can be reduced to Mike Nakis' answer

Answer 2

1. Let n be word.length - 3. (Yes, '3'.)
2. Issue a random index i in the range 0...n.
3. Swap the letters at word[1 + n] and word[1 + n + 1].

you are done.

If there is a possibility that the word may contain two identical letters, then whoever gave you this assignment must first answer what happens with words like "moot". Assuming that they will say "moot" stays same, but "schmoot" must become something other than "schmoot", then:

1.b Check if all letters except first and last are same. If they are, you are done.

2.b Keep repeating step 2 until the letters at word[1 + n] and word[1 + n + 1] are different.