edited by
1,038 views
11 votes
11 votes
You are given two strings $S$ and $T$, each of length $\alpha$, consisting only of lower case English letters $(a,b, \dots ,z)$. Propose an $O(\alpha)$-time algorithm to decide whether $S$ can be obtained by permuting the symbols of $T$. For example, if $S \: = \: \text{ algorithm}$, $T \: = \text{ logarithm}$, your algorithm should return $\text{YES}$; but if $S \: = \text{ trainee}$, $T\: = \text{ retinaa}$, your algorithm should return $\text{NO}$.
edited by

4 Answers

Best answer
16 votes
16 votes
$1)$ Take an array of $26$ elements where 'a' corresponds to index $0$,....,$z$ corresponds to index $25$, initially initialized to all $0$s

$2)$ For the first string, increment the corresponding positions of the array by $1$ corresponding to every character as the string is traversed.

3) For the second string, decrement the corresponding positions of the array by $1$ corresponding to every character as the string is traversed.

$4)$ If all the elements of the array are $0$ finally, then output YES, else NO.
edited by
1 votes
1 votes
It is somewhat like counting sort....

step 1-

take a list an array indexed from 0 to 25 corresponds to a,b,c,d,......z respectively. and initialized each element to 0. take O(1)

step-2-

read each element of T and accordingly increase the corresponding index element by 1 . take O(n) time .

step3-

read each element of the string S and accordingly decrease each element of the arrary take O(n) time.

step4-

read the array if all element of the array is 0 then print yes else no take O(n)time.

Total time=O(n)+O(n)+O(n)=O(n)

space=input (n+n)+ extra(O(n) for array) =O(n)
0 votes
0 votes

permute(String S, String T)
               S = S.toLowerCase();
        T = T.toLowerCase();
        int[] freq = new int[26];
        int len = S.length();
        for(int i = 0; i < len; i++) 
            freq[T.charAt(i) - 'a']++;
        for(int i = 0; i < len; i++) 
            freq[S.charAt(i) - 'a']--;
        for(int i = 0; i < 26; i++)
            if(freq[i] != 0) return "No";
        return "Yes";

    

0 votes
0 votes
Let’s call this function as Ispermutable which takes two input strings 

Ispermutable( string s, string t){
    int n=s.length() , m=t.length() ;
        if(n!=m) return NO;
        int arr[26];
        for(int i=0;i<26;++i) arr[i]=0;
        for(int i=0;i<n;i++) {
        arr[s[i]-97]++;
        arr[t[i]-97]--;
        }
        for(int i=0;i<26;i++){
            if(arr[i]) return NO;
        }
        return YES ;
}

 

Related questions