Find all the permutations of a string - similar to permute arrays

Recursive Solution

Example String: abcdefgh

When i = 0, we have, First wave of recursion till the String is empty

Input String: abcdefgh - ""  +  "bcdefgh" = "bcdefgh"
Input String: bcdefgh - ""  +  "cdefgh"    = "cdefgh"
Input String: cdefgh - ""  +  "defgh"       = "defgh"
Input String: defgh - ""  +  "efgh"           = "efgh"
Input String: efgh - ""  +  "fgh"               = "fgh"
Input String: fgh - ""  +  "gh"                  = "gh"
Input String: gh - ""  +  "h"                     = "h"
Input String: h - ""  +  ""                         = ""

Then coming out of recursion

Input String: gh - "g"  +  "" = "g"
Input String: g - ""  +  "" = ""

Input String: fgh - "f"  +  "h" = "fh"
Input String: fh - ""  +  "h" = "h"
Input String: h - ""  +  "" = ""

Input String: fh - "f"  +  "" = "f"
Input String: f - ""  +  "" = ""

Second round of for loop with i = 2

Input String: abcdefgh - "a"  +  "cdefgh" = "acdefgh"
Input String: acdefgh - ""  +  "cdefgh"     = "cdefgh"
Input String: cdefgh - ""  +  "defgh"        = "defgh"
Input String: defgh - ""  +  "efgh"            = "efgh"
Input String: efgh - ""  +  "fgh"                = "fgh"
Input String: fgh - ""  +  "gh"                   = "gh"
Input String: gh - ""  +  "h"                      = "h"
Input String: h - ""  +  ""                          = ""

And this continues. Here Permutations are printed in order of the string characters and duplicates would be present.
private static void perm1(String prefix, String s) {
    int n = s.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++) {
            perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i + 1, n));
        }
    }
}
Using Array Permutations

We can also convert string to arrays and use permutations on them.


Here though we swap first and last characters recursively decrementing the last pointer, until first is equal to last character. The result for "abc" string is as below:

                         ABC
         /                   |                    \
     ABC             BAC              CBA
    /       \             /      \               /    \
ABC  ACB     BAC BCA    CBA CAB
  
public static void main(String[] args) {
   String string = "abcdefgh";
   perm2(string.toCharArray(), 0, string.length()-1);
}

private static void perm2(char[] a, int start, int end) {
    if (start == end) {
        System.out.println(new String(a));
    }
    else {
        for (int i = start; i <= end; i++) {
            swap(a, start,i);
            permute(a, start+1, end);
            swap(a, start,i);
        }
    }
}

// swap the characters at indices i and j
private static void swap(char[] a, int i, int j) {
    char c = a[i];
    a[i] = a[j];
    a[j] = c;
}

Comments

Post a Comment

Popular posts from this blog

Print staircase with both base and height equal to n

Consider a staircase of size n=4, as shown below:       #     ##   ### #### Observe that its base and height are both equal to n, and the image is drawn using # symbols and spaces. The last line is not preceded by any spaces. Write a program that prints a staircase of size n. public static void main(String[] args) { int n = 10; if(n < 1 || n > 100) { throw new IllegalArgumentException("N should be between 0 and 100"); } for (int i = 1; i <= n; i++) { System.out.println(Stream.concat(Stream.generate(() -> " ").limit(n-i), Stream.generate(() -> "#").limit(i)) .collect(Collectors.joining())); } } }
Read more

Find the maximum occurring character in given String ?

public static void main(String[] args) { System.out.println(maxOccurringChar("122333444455555666666")); } public static Character maxOccurringChar(String s) { Map<Character, Integer> charCountMap = new HashMap<>(); char[] array = s.toCharArray(); for (int i = 0; i < array.length; i++) { if(array[i] != ' ') { Integer occ = charCountMap.getOrDefault(array[i], 0); charCountMap.put(array[i], ++occ); } } Map.Entry<Character, Integer> maxEntry = charCountMap.entrySet().stream() .max(Map.Entry.comparingByValue()).get(); // Map.Entry<Character, Integer> maxEntry = getEntryWithMaxValue(charCountMap); System.out.println(String.format("Character %s occurs %s times.", maxEntry.ge...
Read more

Find the longest substring without repeating characters

Sliding Window is a subarray running on a large array, which is a collection of underlying elements. Here we use two pointers, one pointer A always selects the first char of the max substring, from each iteration of the string. The second pointer B runs ahead of pointer A, until a duplicate character is found or the end of the string is reached. public int lengthOfLongestSubstring(String s) { int a_pointer = 0; int b_pointer = 0; int max = 0; Set<Character> hashSet = new HashSet<>(); int i = 0; while(b_pointer < s.length()) { if(!hashSet.contains(s.charAt(b_pointer))) { hashSet.add(s.charAt(b_pointer)); b_pointer++; max = Math.max(hashSet.size(), max); } else { hashSet.remove(s.charAt(a_pointer)); a_pointer++; } } return max; }
Read more