Given two strings, determine if one is a permutation of the other

Question

After comparing my newbie attempt with other people's answers, I have a couple questions:

• I've made s1_set the size of s1. I've seen other people assume that the strings are ASCII-256 and use s1_set(256) but to me this doesn't make sense. Won't s1_set have at most s1.size() bytes (and fewer if s1 has duplicate characters)?

• I've also seen explicit casting before accessing s1_set: int val = static_cast<int>(x);. Is this necessary? Is it bad form to use implicit casting?

• Would it be preferred to use the regular for statement, or does the range-for work just as well?

#include <iostream>
#include <vector>
using namespace std;
bool is_permutation(const string& s1, const string& s2) {
 if (s1.size() != s2.size()) {
 return false;
 }
 vector<int> s1_set(s1.size());
 for (const auto& x : s1) { 
 ++s1_set[x];
 }
 for (const auto& x : s2) {
 if (--s1_set[x] < 0) {
 return false;
 }
 }
 return true;
}
int main(int argc, char* argv[]) {
 cout << is_permutation("AABC", "BCBA") << endl; // false
 cout << is_permutation("BC", "CBA") << endl; // false, different sizes
 cout << is_permutation("ABC", "CBA") << endl; // true
 cout << is_permutation("AABC", "ACBA") << endl; // true
}

• Morwenn: You could also use std::is_permutation (ok, it surely defeats the purpose), or simply sort copies of both strings and compare them.
• Matthieu: s1_set is the count of each character, so it should be 256 (one bin per possible value). And it should be unsigned char so the index will always be > 0.
• nachocab: Ah, ok, I see what you mean

Answer 1

This code is broken.

// This creates an array with size elements all set to zero.
// But your string (in the examples) are not more than 4 long.
// So the largest vector is 4 elements long.
vector<int> s1_set(s1.size());
// Here x is char.
for (const auto& x : s1) { 
// It is undefined if char is signed or unsigned.
// so the range of values for x is
// 0 -> 255
// or -127 -> 128
//
// Either way the range is well beyond the size of
// the array defined above.

• 200_success: Could you provide an example where the code would produce a wrong result?
• Loki Astari: @200_success: is_permutation("AABC", "BCBA"). It is undefined behavior. It may look correct sometimes but other times it may just fail. The issue is the the input strings are only 4 characters long. s1_set['A']++ will therefore access out side the vector bounds.

Answer 2

I suggest you create an unordered_map<string::value_type, size_t>, which maps each character to the number of its occurrences in a string. Then you compute the histogram of the first string. After that, you iterate through the second string, and for each its character c you decrement map[c]. If, however, before decrementing we have map[c] == 0, then the two strings cannot be each others permutations. The final check is similar.

All in all, I thought about the following:

bool is_permutation2(const string& s1, const string& s2) {
 if (s1.size() != s2.size()) {
 return false;
 }
 std::unordered_map<string::value_type, size_t> map;
 for (const auto& a : s1) {
 map[a]++;
 }
 for (const auto& a : s2) {
 if (map[a] == 0) {
 return false;
 }
 map[a]--;
 }
 return true;
}

Hope that helps.

• nachocab: I think your last for loop is not necessary. Can you think of an example where it would be required? If you remove it, you still get the right answer for these cases: ["AFHJ", "AFH"] // false, ["AAFH", "AHHF"] // false, ["AFHJ", "FHJA"] // true, ["AAHJ", "AHJA"] // true
• coderodde: Yes, you are right. The absence of one character in the 1st string will imply that one character in the 2nd string appears more times than in the 1st string, and as such, will be caught in the second loop.