#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional> // <-- needed for std::function
/*
Function: countNoAdjacentRepeats
--------------------------------
Counts permutations of a string where no two adjacent characters are equal.
Parameters:
s - the input string
Returns:
long long - number of valid permutations
*/
long long countNoAdjacentRepeats(std::string s) {
std::sort(s.begin(), s.end());
int n = s.size();
std::vector<bool> used(n, false);
long long count = 0;
std::string current;
std::function<void()> backtrack = [&]() {
if (current.size() == n) {
count++;
return;
}
for (int i = 0; i < n; i++) {
if (used[i]) continue;
// Avoid duplicates: skip identical characters already used at this level
if (i > 0 && s[i] == s[i - 1] && !used[i - 1]) continue;
if (!current.empty() && current.back() == s[i]) continue;
used[i] = true;
current.push_back(s[i]);
backtrack();
current.pop_back();
used[i] = false;
}
};
backtrack();
return count;
}
int main() {
std::string s = "AABC"; // Example input
/*
Walk-through example for "AABC":
Sorted characters: A A B C
We generate permutations such as:
A A B C <-- rejected (A next to A)
A B A C <-- valid
A B C A <-- valid
A C A B <-- valid
A C B A <-- valid
B A A C <-- rejected (A next to A)
B A C A <-- valid
B C A A <-- rejected (A next to A)
C A A B <-- rejected (A next to A)
C A B A <-- valid
C B A A <-- rejected (A next to A)
Total valid permutations = 6
*/
long long result = countNoAdjacentRepeats(s);
std::cout << "Input string: " << s << std::endl;
std::cout << "Permutations without adjacent repeats: " << result << std::endl;
}
/*
run:
Input string: AABC
Permutations without adjacent repeats: 6
*/
