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.
- "abbccd" , "cbdabc" ,
- Apply negation using s
- Apply negation using v
A possible C++ implementation is shown here