Coding Exercises Round II: #1 in 1 day

Question: Return all given permutations of a string.

import java.util.ArrayList;
import java.util.List;

public class PermuteString {

  private List permutations;

  public PermuteString() {
    permutations = new ArrayList();
  }

  /**
   * Permute a string.
   *
   * @param s
   */
  void permute(String s) {
    permuteString(s, "");
  }

  void permuteString(String remainingLetters, String partialPermutation) {
    if(remainingLetters.length() == 0) {
      permutations.add(partialPermutation);
    }
    else {
      String letter = String.valueOf(remainingLetters.charAt(0));
      remainingLetters = remainingLetters.substring(1);

      if(partialPermutation.length() == 0) {
        permuteString(remainingLetters, letter);
      }
      else {
        for(int j = 0; j <= partialPermutation.length(); j++) {
          String extendedPartialPermutation = partialPermutation.substring(0,j) + 
              letter + partialPermutation.substring(j);

          permuteString(remainingLetters, extendedPartialPermutation);
        }
      }
    }
  }

  public List getPermutations() {
    return permutations;
  }
}