Permutation Of String

Permutations of the Given String

Problem Statement

Given a string S. The task is to print all the possible permutations of the given string.A permutation of a string S iis another string that contains the same characters, only the order of characters can be different.
For example, “abcd” and “dabc” are permutations of each other.

abcd

Examples:
Input: S = “abc”
Output: [“abc”, “acb”, “bac”, “bca”, “cba”, “cab”]
Explanation:
All the permutations of the given string are given.


Approach: Backtracking

Using a backtracking approach, all the permutations of the given string can be printed.
Backtracking is an algorithm for finding all the possible solutions by exploring all possible ways.

Confused about your next job?

In 4 simple steps you can find your personalised career roadmap in Software development for FREE



Expand in New Tab 

If one of the found solutions turns out to not satisfy the given criteria, it discards the solution and makes some changes and backtracks again.

Backtracking

Algorithm:

  • The backtracking function considers the first index of the given string.
  • If the index is N, i.e. length of the string, it means that the current permutation is completed.
  • Run a loop from current index idx till N – 1 and do the following:
    • Swap S[i] and S[idx].
    • Construct all other possible permutations, from backtrack(idx + 1).
    • Backtrack again, i.e. swap(S[i], S[idx]).

C++Implementation For Backtracking Method

void backtrack(string s, int idx, int N) {
    if (idx == N)
      cout << s << endl;
    else {
      for (int i = idx; i <= N; i++) {
        swap(s[idx], a[i]);
        permute(s, idx + 1, N);
        swap(s[idx], a[i]);
      }
    }
    solve() {
      string s = ”ABC”;
      int N = s.length();
      backtrack(s, 0, N - 1);
    }

JavaImplementation For Backtracking Method

 public 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);
}
private void backtrack(String s, int idx, int N) {
  if (idx == N)
    System.out.println(s);
  else {
    for (int i = idx; i <= N; i++) {
      s = swap(s, idx, i);
      backtrack(s, idx + 1, N);
      s = swap(s, idx, i);
    }
  }
}
solve() {
  String s = ”ABC”;
  int N = s.length;
  backtrack(s, 0, N - 1);
}

PythonImplementation For Backtracking Method

def toString(List):
    return ''.join(List)
 
def backtrack(s, idx, N):
    if idx == N:
        print(toString(s))
    else:
        for i in xrange(idx, N + 1):
            s[idx], s[i] = s[i], s[idx]
            backtrack(s, idx + 1, N)
            s[idx], s[i] = s[i], s[idx]
 
 
def solve():
    a = "ABC"
    N = len(s)
    s = list(a)
    permute(s, 0, N - 1)

Time Complexity: O(N * N!), where N is the length of the string.
Space Complexity: O(N!), since one has to keep N! solutions.


Practice Question


FAQs

Q.1: How to print a unique permutation of a string?

Ans: To print the unique permutations of the string, put the strings in a HashSet, hence it will give all unique permutations of the strings.

Q.2: What is the approach used to find permutations of a string?

Ans: The backtracking algorithm is to solve this problem.

Previous Post
Data Warehouse Architecture

Data Warehouse Architecture – Detailed Explanation

Next Post
Edit Distance Problem

Edit Distance Problem

Total
0
Share