Print all Permutations of A String

PHOTO EMBED

Sun Feb 06 2022 22:26:48 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #gfg #geeksforgeeks #lecture #recursion #stringpermutations

public class Permutation
{
	public static void main(String[] args)
	{
		String str = "ABC";
		int n = str.length();
		Permutation permutation = new Permutation();
		permutation.permute(str, 0, n-1);
	}

	/**
	* permutation function
	* @param str string to calculate permutation for
	* @param l starting index
	* @param r end index
	*/
	private void permute(String str, int l, int r)
	{
		if (l == r)
			System.out.println(str);
		else
		{
			for (int i = l; i <= r; i++)
			{
				str = swap(str,l,i);
				permute(str, l+1, r);
				str = swap(str,l,i);
			}
		}
	}

	/**
	* Swap Characters at position
	* @param a string value
	* @param i position 1
	* @param j position 2
	* @return swapped string
	*/
	public String swap(String a, int i, int j)
	{
		char[] arr = a.toCharArray();
		char temp = arr[i] ;
		arr[i] = arr[j];
		arr[j] = temp;
		return String.valueOf(arr);
	}

}
content_copyCOPY

Algorithm Paradigm: Backtracking Time Complexity: O(n*n!) Note that there are n! permutations and it requires O(n) time to print a permutation. Auxiliary Space: O(r – l) Note: The above solution prints duplicate permutations if there are repeating characters in the input string. Examples : Input : s = "ABC" Output : ABC ACB BAC BCA CBA CAB Input : s = "ABC" Output : AB BA Input : s = " " Output : // Nothing to be printed

https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/