#include #include #include #include #include // Use unordered_map for potentially faster average time complexity #include // Required for vector operations using namespace std; // Custom hash function structure for vector to use it as a key in unordered_map. // This is a common approach using XOR and bit shifts to combine element hashes. struct VectorHasher { size_t operator()(const vector& V) const { size_t hash = V.size(); for(const auto &i : V) { // A common hash combining technique. // The constant 0x9e3779b9 is related to the golden ratio and helps distribute hash values. hash ^= i + 0x9e3779b9 + (hash << 6) + (hash >> 2); } return hash; } }; // Helper function to convert character 'A' or 'B' to integer 0 or 1. // Using inline suggests the compiler to replace calls with function body if possible, potentially reducing overhead. inline int char_to_int(char c) { // 'A' maps to 0, 'B' maps to 1 return (c == 'B'); } // Function to compute the difference array `d`. // The k-th element d[k] (0-based index) represents whether S[k] and S[k+1] are different. // d[k] = S_k XOR S_{k+1} (using 0/1 representation for A/B). vector compute_diff_array(const string& s) { int n = s.length(); // The difference array has length N-1. vector d(n - 1); for (int i = 0; i < n - 1; ++i) { // Calculate difference using XOR on integer representations. d[i] = char_to_int(s[i]) ^ char_to_int(s[i+1]); } return d; } int main() { // Use fast I/O operations. ios_base::sync_with_stdio(false); cin.tie(NULL); int n; // Length of the strings cin >> n; string s_str, t_str; // Input strings S and T cin >> s_str >> t_str; // A necessary condition for transformation is that the first and last characters must match. // These characters can never be changed by the operation. if (s_str[0] != t_str[0] || s_str[n - 1] != t_str[n - 1]) { cout << -1 << endl; // If they don't match, transformation is impossible. return 0; } // Compute the difference arrays for the initial string S and target string T. // The state transformation problem can be reformulated in terms of difference arrays. vector d_s = compute_diff_array(s_str); vector d_t = compute_diff_array(t_str); // If the difference arrays are already identical, no operations are needed. if (d_s == d_t) { cout << 0 << endl; return 0; } // Use Breadth-First Search (BFS) to find the shortest path in the state space. // The state is represented by the difference array. // `dist` stores the minimum distance (number of operations) from the initial state `d_s` to any reachable state. // `unordered_map` is used for efficient average time lookup of visited states. unordered_map, int, VectorHasher> dist; queue> q; // Queue for BFS states to visit. dist[d_s] = 0; // Distance to the starting state is 0. q.push(d_s); // Add the starting state to the queue. int final_dist = -1; // Initialize final distance to -1 (target not reached yet). // Standard BFS loop. while (!q.empty()) { vector current_d = q.front(); // Get the current state (difference array). q.pop(); // Remove it from the queue. int current_dist = dist[current_d]; // Get the distance to the current state. // Check if the current state is the target state. if (current_d == d_t) { final_dist = current_dist; // Target found, record the distance. break; // Exit BFS since we found the shortest path. } // Explore neighbors by applying possible operations. // The operation involves choosing an index `i` from 1 to N-2. // The operation is possible if S[i] == S[i+2]. // In terms of the difference array, this condition is equivalent to d[i-1] == d[i]. // Note: String indices are 0 to N-1. Difference array indices are 0 to N-2. // Problem index i=1..N-2 corresponds to S[i], S[i+1], S[i+2]. // Affects difference array at indices i-1 and i (0-based). for (int i = 1; i <= n - 2; ++i) { // Check the condition d[i-1] == d[i]. Indices are 0-based. if (current_d[i-1] == current_d[i]) { vector next_d = current_d; // Create a copy of the current state to modify. // The operation flips S[i+1]. This flips d[i-1] and d[i]. // Flip the corresponding elements in the difference array copy. next_d[i-1] = 1 - next_d[i-1]; // Flip bit (0 becomes 1, 1 becomes 0) next_d[i] = 1 - next_d[i]; // Flip bit // Check if the resulting state `next_d` has been visited before. // `find` checks existence. `dist.end()` means not found. if (dist.find(next_d) == dist.end()) { dist[next_d] = current_dist + 1; // Record the distance to the new state. q.push(next_d); // Add the new state to the queue for exploration. } // If already visited, we ignore it because BFS guarantees that the first time we visit a state, // it is via a shortest path from the source. } } } // After BFS completes, output the found distance. // If `final_dist` is still -1, it means the target state `d_t` was unreachable. cout << final_dist << endl; return 0; }