String Permutations Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/string-permutations

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a string s with distinct lowercase English characters, find all the permutations of s.

Approach

In this problem both the naive and the optimal approaches are equivalent. We can sort the given string lexicographically and try to generate its next greater permutation, till no other permutation remains.

Analysis

• Time Complexity: O(n * n!)
• Space Complexity: O(n * n!)

Implementation

C++

vector<string> result;
void permute(string s, string possible) {
	if(s.size() == 0) {
		result.push_back(possible);
		return;
	}
	for(int i = 0; i < s.size(); i++) {
		string left = s.substr(0, i);
		string right = s.substr(i + 1, s.size() - i - 1);
		string total = left + right;
		permute(total, possible + s[i]);
	}
}
vector<string> getAllPermutations(string s) {
	result.clear();
	sort(s.begin(), s.end());
	permute(s, "");
	return result;
}

Java

class Solution {
	static List<String> getAllPermutations(String s) {
		ArrayList<String> arr = new ArrayList<>();
		permute(s, 0, s.length() - 1, arr);
		return arr;
	}
	public static void permute(String s, int left, int right,ArrayList<String> arr) {
        if (left == right) {
            arr.add(s);
		}
        else {
            for (int i = left; i <= right; i++) {
                s = swap(s, left, i);
                permute(s, left+1, right,arr);
                s = swap(s, left, i);
            }
        }
    }
    public static String swap(String a, int i, int j) {
        char temp;
        char[] charArray = a.toCharArray();
        temp = charArray[i] ;
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return String.valueOf(charArray);
    }
}