Anagram | Lei Jiang Coding
Sid is obsessed with reading short stories. Being a CS student, he is doing some interesting frequency analysis with the books. He chooses strings S1 and S2 in such a way that |len(S1)−len(S2)|≤1.
Your task is to help him find the minimum number of characters of the first string he needs to change to enable him to make it an anagram of the second string.
aaabbb
ab
abc
mnop
xyyx
xaxbbbxx
3
1
-1
2
0
1
Test Case #01: We have to replace at least three characters from any of the string to make both of strings anagram. Here, a = “aaa” and b = “bbb”. One possible solution is to replace all character ‘a’ in string a with character ‘b’.
Test Case #02: Either replace ‘a’ with ‘b’, which will generate “bb”. Or replace ‘b’ with ‘a’ to generate “aa”. Both of the solution are valid.
Test Case #03: It is not possible for two strings of unequal length to be anagram for each other.
Test Case #04: We have to replace both the characters of any string to make it anagram of other one.
Test Case #05: _S1_ and S2 are already anagram to each other.
Test Case #06: Here S1 = “xaxb” and S2 = “bbxx”. He had to replace ‘a’ from S1 with ‘b’ so thatS1 = “xbxb” and we can rearrange its letter to “bbxx” in order to get S2.
Read full article from Anagram | Lei Jiang Coding
Sid is obsessed with reading short stories. Being a CS student, he is doing some interesting frequency analysis with the books. He chooses strings S1 and S2 in such a way that |len(S1)−len(S2)|≤1.
Your task is to help him find the minimum number of characters of the first string he needs to change to enable him to make it an anagram of the second string.
aaabbb
ab
abc
mnop
xyyx
xaxbbbxx
3
1
-1
2
0
1
Test Case #01: We have to replace at least three characters from any of the string to make both of strings anagram. Here, a = “aaa” and b = “bbb”. One possible solution is to replace all character ‘a’ in string a with character ‘b’.
Test Case #02: Either replace ‘a’ with ‘b’, which will generate “bb”. Or replace ‘b’ with ‘a’ to generate “aa”. Both of the solution are valid.
Test Case #03: It is not possible for two strings of unequal length to be anagram for each other.
Test Case #04: We have to replace both the characters of any string to make it anagram of other one.
Test Case #05: _S1_ and S2 are already anagram to each other.
Test Case #06: Here S1 = “xaxb” and S2 = “bbxx”. He had to replace ‘a’ from S1 with ‘b’ so thatS1 = “xbxb” and we can rearrange its letter to “bbxx” in order to get S2.
int
Anagram(string s){
if
(s.size() & 1)
return
-1;
int
n = s.size() / 2;
string s1 = s.substr(0, n);
string s2 = s.substr(n);
int
map[N] = {0};
for
(
int
i = 0; i < n; ++i){
map[s1[i] -
'a'
]++;
map[s2[i] -
'a'
]--;
}
int
count = 0;
for
(
int
i = 0; i < N; ++i){
//cout << map[i];
if
(map[i] > 0)
count += map[i];
}
//cout << endl;
return
count;
}
Read full article from Anagram | Lei Jiang Coding