Posts Self Permutation (InterviewBit)
Post
Cancel

Self Permutation (InterviewBit)

PROBLEM DESCRIPTION

You are given two strings A and B. Check whether there exists any permutation of both A and B such that they are equal.

Return a single integer 1 if its exists, 0 otherwise.

SOLUTION

APPROACH 1

Sorted form of both string should be same.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {

    public int permuteStrings(String A, String B) {

        int n = A.length();
        int m = B.length();

        if(n != m)
            return 0;

        char[] charArray1 = A.toCharArray();
        Arrays.sort(charArray1);

        char[] charArray2 = B.toCharArray();
        Arrays.sort(charArray2);

        for(int i=0; i<n; i++){
            if(charArray1[i] != charArray2[i])
                return 0;
        }

        return 1;

    }

}

APPROACH 2

Frequency of any character from a to z should be same in both strings.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {

    public int permuteStrings(String A, String B) {

        int n = A.length();
        int m = B.length();

        if(n != m)
            return 0;

        int[] freq = new int[26];

        for(int i=0; i<n; i++){
            freq[A.charAt(i)-'a']++; // increase freq of char in A
            freq[B.charAt(i)-'a']--; // decrease freq of char in B
        }

        // if freq of all characters are same in A and B
        // the net sum should be 0 for each char from a to z
        // if not, there must be some difference in the chars between them
        // in that case, same permutation cannot be formed
        for(int i=0; i<26; i++){
            if(freq[i] != 0)
                return 0;
        }

        return 1;

    }

}
This post is licensed under CC BY 4.0 by the author.