# Check if Strings Can be Made Equal With Operations I
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-strings-can-be-made-equal-with-operations-i)
Canonical: https://scaleengineer.com/dsa/problems/check-if-strings-can-be-made-equal-with-operations-i
**Data structures:** String
**Companies:** [Citrix](https://scaleengineer.com/companies/citrix)
---
## Problem
You are given two strings `s1` and `s2`, both of length `4`, consisting of **lowercase** English letters.

You can apply the following operation on any of the two strings **any** number of times:

* Choose any two indices `i` and `j` such that `j - i = 2`, then **swap** the two characters at those indices in the string.

Return `true` _if you can make the strings_ `s1` _and_ `s2` _equal, and_ `false` _otherwise_.

**Example 1:**

**Input:** s1 = "abcd", s2 = "cdab"
**Output:** true
**Explanation:** We can do the following operations on s1:
- Choose the indices i = 0, j = 2. The resulting string is s1 = "cbad".
- Choose the indices i = 1, j = 3. The resulting string is s1 = "cdab" = s2.

**Example 2:**

**Input:** s1 = "abcd", s2 = "dacb"
**Output:** false
**Explanation:** It is not possible to make the two strings equal.

**Constraints:**

* `s1.length == s2.length == 4`
* `s1` and `s2` consist only of lowercase English letters.

# Approaches
## BFS State Space Search
This approach models the problem as a graph traversal problem. Each possible string configuration is a node in the graph, and an edge exists between two nodes if one can be transformed into the other by a single valid swap operation. We can use a search algorithm like Breadth-First Search (BFS) to explore all reachable strings starting from `s1` and see if `s2` is among them.
**Time:** O(1). The number of states in our graph is constant. For each state, we do a constant amount of work (swaps, string creations, comparisons, hash set operations). Thus, the overall time complexity is constant. · **Space:** O(1). Since the string length is fixed at 4, the total number of reachable states is also a small constant (at most 4). Therefore, the space required for the queue and the set is constant.
**Pros:** It is a very general method that can be applied to a wide range of state-space search problems.; It is guaranteed to find a solution if one exists.
**Cons:** This approach is overly complex for a problem with such a small and fixed state space.; It has higher constant factor overhead due to the use of a queue, a set, and repeated string manipulations (creation, hashing).
### Explanation
We can treat this problem as finding a path from a start node (`s1`) to a target node (`s2`) in a state-space graph. The BFS algorithm is a perfect fit for finding if a path exists.

1.  We start with a queue containing just `s1`.
2.  We also use a `Set` to keep track of strings we've already processed to prevent getting into infinite loops (though not possible here, it's good practice) and to avoid redundant work.
3.  The algorithm proceeds by taking a string from the queue, generating all possible strings that can be formed from it in one step (by swapping indices 0 and 2, or 1 and 3), and adding these new strings to the queue if they haven't been visited yet.
4.  If at any point we generate or encounter `s2`, we know it's possible to transform `s1` into `s2`, and we can immediately return `true`.
5.  If the queue runs out of strings to process and we have not found `s2`, it means `s2` is unreachable, so we return `false`.

```java
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution {
    private String swap(String s, int i, int j) {
        char[] chars = s.toCharArray();
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
        return new String(chars);
    }

    public boolean canBeEqual(String s1, String s2) {
        if (s1.equals(s2)) {
            return true;
        }

        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        queue.add(s1);
        visited.add(s1);

        while (!queue.isEmpty()) {
            String current = queue.poll();

            // Generate neighbors by applying the two possible swaps
            String neighbor1 = swap(current, 0, 2);
            if (neighbor1.equals(s2)) return true;
            if (!visited.contains(neighbor1)) {
                queue.add(neighbor1);
                visited.add(neighbor1);
            }

            String neighbor2 = swap(current, 1, 3);
            if (neighbor2.equals(s2)) return true;
            if (!visited.contains(neighbor2)) {
                queue.add(neighbor2);
                visited.add(neighbor2);
            }
        }

        return false;
    }
}
```
### Algorithm
- Initialize a queue for Breadth-First Search (BFS) and add the initial string `s1`.
- Initialize a `Set` to store visited strings to avoid cycles and redundant processing, and add `s1` to it.
- Loop while the queue is not empty:
  - Dequeue a string, `current`.
  - If `current` is equal to `s2`, a valid sequence of operations has been found, so return `true`.
  - Generate two potential next states from `current`:
    1. `next1`: by swapping characters at indices 0 and 2.
    2. `next2`: by swapping characters at indices 1 and 3.
  - For each generated state, if it has not been visited before, add it to the queue and the visited set.
- If the queue becomes empty and `s2` has not been reached, it's impossible to make the strings equal, so return `false`.

## Generate and Compare Transformations
A more direct approach is to realize that from any given string `s1`, we can only generate a small, finite set of other strings. The operations partition the string's characters into two independent groups: those at even indices (0, 2) and those at odd indices (1, 3). Within each group, the two characters can either stay in place or be swapped. This results in at most 4 unique strings that can be formed from `s1`. We can simply generate all of them and check if `s2` is one of them.
**Time:** O(1). We perform a constant number of swaps, string creations, and comparisons. Since the string length is fixed at 4, all operations take constant time. · **Space:** O(1). We create a few character arrays of constant size (4), so the space usage is constant.
**Pros:** Much simpler to implement and reason about than a full graph search.; Directly enumerates all possibilities, which is feasible for a small state space.
**Cons:** Involves creating new string or character array objects, which can be slightly less performant than direct memory access and comparison.; The logic can be a bit verbose, checking four distinct cases.
### Explanation
The core idea is that any string reachable from `s1` must be one of four possibilities, based on whether we swap the even-indexed characters, the odd-indexed characters, both, or neither.

1.  **No swaps:** The string remains `s1`.
2.  **Even swap only:** Swap `s1[0]` and `s1[2]`.
3.  **Odd swap only:** Swap `s1[1]` and `s1[3]`.
4.  **Both swaps:** Swap `s1[0]` with `s1[2]` AND `s1[1]` with `s1[3]`.

We can systematically check if `s2` matches any of these four configurations of `s1`.

```java
class Solution {
    public boolean canBeEqual(String s1, String s2) {
        // Case 1: s1 is already equal to s2 (no swaps)
        if (s1.equals(s2)) {
            return true;
        }

        char[] s1Chars = s1.toCharArray();

        // Case 2: Swap even indices (0 and 2)
        char[] s1EvenSwapped = s1Chars.clone();
        char temp = s1EvenSwapped[0];
        s1EvenSwapped[0] = s1EvenSwapped[2];
        s1EvenSwapped[2] = temp;
        if (new String(s1EvenSwapped).equals(s2)) {
            return true;
        }

        // Case 3: Swap odd indices (1 and 3)
        char[] s1OddSwapped = s1Chars.clone();
        temp = s1OddSwapped[1];
        s1OddSwapped[1] = s1OddSwapped[3];
        s1OddSwapped[3] = temp;
        if (new String(s1OddSwapped).equals(s2)) {
            return true;
        }

        // Case 4: Swap both even and odd indices
        char[] s1BothSwapped = s1EvenSwapped.clone(); // Start from the even-swapped version
        temp = s1BothSwapped[1];
        s1BothSwapped[1] = s1BothSwapped[3];
        s1BothSwapped[3] = temp;
        if (new String(s1BothSwapped).equals(s2)) {
            return true;
        }

        return false;
    }
}
```
### Algorithm
- Start with the original string `s1`.
- Check if `s1` is already equal to `s2`. If yes, return `true`.
- Generate a new string by swapping characters at indices 0 and 2 of `s1`. Check if this new string equals `s2`. If yes, return `true`.
- Generate another new string by swapping characters at indices 1 and 3 of the original `s1`. Check if this equals `s2`. If yes, return `true`.
- Finally, generate a string by performing both swaps (swap 0 and 2, then swap 1 and 3). Check if this equals `s2`. If yes, return `true`.
- If none of the above four possibilities match `s2`, return `false`.

## Direct Character Comparison
The most efficient approach is based on a key insight about the allowed operations. The swap operation `j - i = 2` means we can only swap characters at indices (0, 2) and (1, 3). This effectively partitions the string's characters into two independent sets: `{s[0], s[2]}` and `{s[1], s[3]}`. For `s1` to be transformable into `s2`, the multiset of characters at even positions in `s1` must match the multiset of characters at even positions in `s2`. The same must hold true for the characters at odd positions.
**Time:** O(1). The solution consists of a fixed number of character accesses and boolean operations, which is constant time. · **Space:** O(1). This approach uses no extra space that scales with input size. It only reads from the input strings.
**Pros:** Extremely efficient in both time and space as it only involves a few character comparisons.; No new objects or data structures are created, leading to minimal overhead.; The code is clean, concise, and directly implements the core logic of the problem.
**Cons:** The solution is highly specific to the problem's constraints (string length 4, swap distance 2) and is not easily generalizable to different rules.
### Explanation
This method avoids any string creation or complex data structures. It directly compares the characters based on the logical partitioning of the string.

The characters at indices 0 and 2 form one group. The characters at indices 1 and 3 form another. A character can never move from an even index to an odd index or vice-versa.

Therefore, for `s1` to be transformable into `s2`, two things must be true:
1.  The pair of characters `{s1[0], s1[2]}` must be a permutation of the pair `{s2[0], s2[2]}`.
2.  The pair of characters `{s1[1], s1[3]}` must be a permutation of the pair `{s2[1], s2[3]}`.

We can check these two conditions with a simple boolean expression. For two pairs of characters `{a, b}` and `{c, d}` to be permutations of each other, it must be that either `a=c` and `b=d`, or `a=d` and `b=c`. We apply this logic to both the even-indexed and odd-indexed characters.

```java
class Solution {
    public boolean canBeEqual(String s1, String s2) {
        // Check if the multiset of characters at even positions are the same.
        // This means (s1[0], s1[2]) is a permutation of (s2[0], s2[2]).
        boolean evenMatch = (s1.charAt(0) == s2.charAt(0) && s1.charAt(2) == s2.charAt(2)) ||
                            (s1.charAt(0) == s2.charAt(2) && s1.charAt(2) == s2.charAt(0));

        // Check if the multiset of characters at odd positions are the same.
        // This means (s1[1], s1[3]) is a permutation of (s2[1], s2[3]).
        boolean oddMatch = (s1.charAt(1) == s2.charAt(1) && s1.charAt(3) == s2.charAt(3)) ||
                           (s1.charAt(1) == s2.charAt(3) && s1.charAt(3) == s2.charAt(1));

        // Both conditions must be true.
        return evenMatch && oddMatch;
    }
}
```
### Algorithm
- The problem can be solved by checking two independent conditions:
  1. The multiset of characters at even indices (0 and 2) in `s1` must be the same as the multiset of characters at even indices in `s2`.
  2. The multiset of characters at odd indices (1 and 3) in `s1` must be the same as the multiset of characters at odd indices in `s2`.
- To check the first condition, we verify if `(s1[0] == s2[0] AND s1[2] == s2[2])` OR `(s1[0] == s2[2] AND s1[2] == s2[0])`.
- To check the second condition, we verify if `(s1[1] == s2[1] AND s1[3] == s2[3])` OR `(s1[1] == s2[3] AND s1[3] == s2[1])`.
- The function returns `true` only if both conditions are met, otherwise it returns `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean canBeEqual(String s1, String s2) {
    int[][] cnt = new int[2][26];
    for (int i = 0; i < s1.length(); ++i) {
      ++cnt[i & 1][s1.charAt(i) - 'a'];
      --cnt[i & 1][s2.charAt(i) - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
      if (cnt[0][i] != 0 || cnt[1][i] != 0) {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool canBeEqual(string s1, string s2) {
    vector<vector<int>> cnt(2, vector<int>(26, 0));
    for (int i = 0; i < s1.size(); ++i) {
      ++cnt[i & 1][s1[i] - 'a'];
      --cnt[i & 1][s2[i] - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
      if (cnt[0][i] || cnt[1][i]) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def canBeEqual(self, s1: str, s2: str) -> bool: return sorted(
        s1[:: 2]) == sorted(s2[:: 2]) and sorted(s1[1:: 2]) == sorted(s2[1:: 2])

```