Programming Interview Question

Question: given two string write a method to decide if one is a permutation of the other.

This is a common question that could be easily solved if we know in advance which is the size of the alphabeth. A straightforward approach could be to sort both strings and then compare them. This approach has complexity  due to sorting. We can do better and lower the complexity to  if we reason as follows: given a boolean sequence of the same size of the alphabet  initially false initialized.  Then what happen if  for each char we found in the  string  we negate the value of the correnspoding bool in the sequence? We end up having the  at position  if the char  appeared an odd number of times and  otherwise. Now if the other string  is a permutation of the first one, we all agree that for each char in  it contains the same number of occurrences. This means that if we apply the same process as before on the boolean sequence using as input the string  each bool is being negated an even number of times and this means that its value would be the same as the beginning of the process (all ). So if the sequence does not contains any true value, than it means that the strings contains the same elements i.e. they are permutation of each other.

Example:

1. "abbccd" ,  "cbdabc" , 
2. Apply negation using s
• 
3. Apply negation using v
• 

A possible C++ implementation is shown here

template<uint SIZEALPHABETH = 256>
bool isPermutation(const std::string& v, const std::string& s){

if(v.size() != s.size())
return false;
bool counters[SIZEALPHABETH] = { 0 };

for(uint j=0 ; j<s.size() ; j++){
uint idxs= s[j]%SIZEALPHABETH;
uint idxv= v[j]%SIZEALPHABETH;
counters[idxs] = !counters[idxs];
counters[idxv] = !counters[idxv];
}
for(uint j=0 ; j<SIZEALPHABETH ; j++)
if(counters[j])
return false;

return true;

}

Be the first to leave a comment. Don’t be shy.