Check if Strings Can be Made Equal With Operations I

Easy
1760.

Check if Strings Can be Made Equal With Operations I

Check if Strings Can be Made Equal With Operations I is an easy coding problem on strings, asked in Google interviews.

You are given two strings s1 and s2, each of length exactly 4 and made of lowercase letters.

You may apply the following operation to either string as many times as you like: pick two indices i and j with j - i = 2 and swap the characters at those indices.

Return true if you can make s1 and s2 equal, and false otherwise.

Example 1

Input
s1 = "abcd", s2 = "cdab"
Output
true
Explanation
Swap indices 0 and 2 of s1 to get "cbad", then indices 1 and 3 to get "cdab".

Example 2

Input
s1 = "abcd", s2 = "dacb"
Output
false
Explanation
Index 0 of s2 holds 'd', but only 'a' or 'c' can ever reach index 0 of s1.

Example 3

Input
s1 = "kair", s2 = "kair"
Output
true
Explanation
The strings are already equal; no operation is needed.

Constraints

  • s1.length == s2.length == 4
  • s1 and s2 consist only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var canBeEqual = function(s1, s2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Check if Strings Can be Made Equal With Operations I Solution

Check if Strings Can be Made Equal With Operations I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Check if Strings Can be Made Equal With Operations I is an easy coding problem on strings, asked in Google interviews.

  • Difficulty: Easy
  • Topics: Strings
  • Asked at: Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given two strings s1 and s2, each of length exactly 4 and made of lowercase letters.

You may apply the following operation to either string as many times as you like: pick two indices i and j with j - i = 2 and swap the characters at those indices.

Return true if you can make s1 and s2 equal, and false otherwise.

Example 1

Input: s1 = "abcd", s2 = "cdab"
Output: true
Explanation: Swap indices 0 and 2 of s1 to get "cbad", then indices 1 and 3 to get "cdab".

Example 2

Input: s1 = "abcd", s2 = "dacb"
Output: false
Explanation: Index 0 of s2 holds 'd', but only 'a' or 'c' can ever reach index 0 of s1.

Example 3

Input: s1 = "kair", s2 = "kair"
Output: true
Explanation: The strings are already equal; no operation is needed.

Constraints

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

Hints for Check if Strings Can be Made Equal With Operations I

  1. Hint 1

    A swap with j - i = 2 only ever moves characters between index 0 and index 2, or between index 1 and index 3.

  2. Hint 2

    So each string splits into two independent pairs: positions {0, 2} and positions {1, 3}. Within a pair the two characters can be in either order.

  3. Hint 3

    The strings can be made equal exactly when the pair at {0, 2} holds the same two characters in both strings, and likewise for {1, 3}.

How to solve Check if Strings Can be Made Equal With Operations I

The allowed swaps never mix the even positions with the odd positions; within each group of two the characters can be ordered freely. So all that matters is the unordered pair at {0, 2} and the unordered pair at {1, 3}.

Approach

  1. Check that {s1[0], s1[2]} equals {s2[0], s2[2]} as an unordered pair — either s1[0] == s2[0] && s1[2] == s2[2] or the crossed version.
  2. Check the same for indices 1 and 3.
  3. Return true only if both checks pass.

Why it works

Each operation permutes the characters inside one of the two groups, so the multiset of each group is invariant — the condition is necessary. It is also sufficient: if a group's characters are the same two but in the other order, one swap on s1 fixes it.

Complexity

  • Time — O(1)
  • Space — O(1)

Pitfalls

  • Comparing the sorted whole strings is wrong — a character cannot move from an even to an odd index ("abcd" vs "badc" is false).

Reference solution

Python

def canBeEqual(s1: str, s2: str) -> bool:
    def same(i: int, j: int) -> bool:
        return (s1[i] == s2[i] and s1[j] == s2[j]) or (s1[i] == s2[j] and s1[j] == s2[i])
    return same(0, 2) and same(1, 3)

Java

public static boolean canBeEqual(String s1, String s2) {
    return same(s1, s2, 0, 2) && same(s1, s2, 1, 3);
}

static boolean same(String a, String b, int i, int j) {
    return (a.charAt(i) == b.charAt(i) && a.charAt(j) == b.charAt(j))
        || (a.charAt(i) == b.charAt(j) && a.charAt(j) == b.charAt(i));
}

C++

bool canBeEqual(string s1, string s2) {
    auto same = [&](int i, int j) {
        return (s1[i] == s2[i] && s1[j] == s2[j]) || (s1[i] == s2[j] && s1[j] == s2[i]);
    };
    return same(0, 2) && same(1, 3);
}

JavaScript

var canBeEqual = function(s1, s2) {
    var same = function(i, j) {
        return (s1[i] === s2[i] && s1[j] === s2[j]) || (s1[i] === s2[j] && s1[j] === s2[i]);
    };
    return same(0, 2) && same(1, 3);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings