String Permutation II

Given a string, find all permutations of it without duplicates.

Example:

Given "abb", return ["abb", "bab", "bba"].

Given "aabb", return ["aabb", "abab", "baba", "bbaa", "abba", "baab"].

Solution:

Similar idea to Next Permutation.

1. sort the input string
2. calculate the next permutation
3. when string is in decending order (couldn't find the last increasing trend from the back), stop.

Code:

public class Solution {

    public List<String> stringPermutation2(String str) {
        List<String> res = new ArrayList<>();
        if (str == null || str.length() <= 1) {
            res.add(str);
            return res;
        }
        char[] s = str.toCharArray();
        Arrays.sort(s);
        res.add(new String(s));
        while ((s = nextPermutation(s)) != null) {
            res.add(new String(s));
        }
        return res;
    }

    private char[] nextPermutation(char[] chars) {
        int index = -1;
        for (int i = chars.length - 1; i > 0; i--) {
            if (chars[i] > chars[i - 1]) {
                index = i - 1;
                break;
            }
        }
        if (index == -1) {
            return null;
        }
        int biggerIndex = index + 1;
        for (int i = chars.length - 1; i > index; i--) {
            if (chars[i] > chars[index]) {
                biggerIndex = i;
                break;
            }
        }
        swap(chars, index, biggerIndex);
        reverse(chars, index + 1, chars.length - 1);
        return chars;
    }

    private void reverse(char[] chars, int start, int end) {
        while (start < end) {
            swap(chars, start, end);
            start++;
            end--;
        }
    }

    private void swap(char[] chars, int a, int b) {
        char temp = chars[a];
        chars[a] = chars[b];
        chars[b] = temp;
    }

}