Check if Strings Can be Made Equal With Operations II

Check if Strings Can be Made Equal With Operations II - Problem

You are given two strings s1 and s2, both of length n, 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 i < j and the difference j - i is even, 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.

Input & Output

Example 1 — Basic Case

$ Input: s1 = "abc", s2 = "bac"

› Output: true

💡 Note: We can swap s1[0] and s1[2] (distance 2 is even) to get "cba", then swap s1[1] and s1[2] (distance 1 is odd, so this won't work). Actually, let's check frequencies: Even positions - s1: 'a','c' vs s2: 'b','c'. They don't match, so this should be false.

Example 2 — Same Characters Different Order

$ Input: s1 = "abcde", s2 = "caebd"

› Output: false

💡 Note: Even positions: s1 has 'a','c','e' vs s2 has 'c','e','d'. Different frequencies, so impossible to make equal.

Example 3 — Already Equal

$ Input: s1 = "abc", s2 = "abc"

› Output: true

💡 Note: Strings are already equal, so no operations needed.

Constraints

1 ≤ n ≤ 10⁵
s1.length == s2.length == n
s1 and s2 consist only of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings s1 and s2 of equal length

Constraint

Can only swap positions where j-i is even

Key Insight

Even and odd positions form separate groups

Key Takeaway

🎯 Key Insight: Even-distance swaps keep even and odd positions separate, so we only need to check character frequency equality within each parity group

Asked in

G Google 12 M Microsoft 8

The key insight is that swaps with even distance preserve position parity - even positions can only swap with other even positions, and odd positions can only swap with other odd positions. Best approach is frequency counting by position parity. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(2^n)	O(2^n)	Try all possible swaps until strings match or no more swaps possible
Character Frequency Analysis	O(n)	O(1)	Count character frequencies at even and odd positions separately

Brute Force Simulation — Algorithm Steps

Try all possible swaps with even distance
Recursively check if any resulting state can reach target
Return true if target is reachable

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with s1 = 'abc', s2 = 'bac'

Try Swaps

Try swapping positions with even distance

Recursively Explore

For each swap, recursively try more swaps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_VISITED 10000

char visited[MAX_VISITED][1001];
int visitedCount = 0;

bool isVisited(char* str) {
    for (int i = 0; i < visitedCount; i++) {
        if (strcmp(visited[i], str) == 0) {
            return true;
        }
    }
    return false;
}

void addVisited(char* str) {
    if (visitedCount < MAX_VISITED) {
        strcpy(visited[visitedCount++], str);
    }
}

bool canTransform(char* current, char* target) {
    if (strcmp(current, target) == 0) return true;
    if (isVisited(current)) return false;
    
    addVisited(current);
    int len = strlen(current);
    
    // Try all possible swaps with even distance
    for (int i = 0; i < len; i++) {
        for (int j = i + 2; j < len; j += 2) {
            // Swap
            char temp = current[i];
            current[i] = current[j];
            current[j] = temp;
            
            if (canTransform(current, target)) {
                return true;
            }
            
            // Backtrack
            temp = current[i];
            current[i] = current[j];
            current[j] = temp;
        }
    }
    
    return false;
}

bool solution(char* s1, char* s2) {
    if (strlen(s1) != strlen(s2)) return false;
    visitedCount = 0;
    char temp[1001];
    strcpy(temp, s1);
    return canTransform(temp, s2);
}

int main() {
    char s1[1001], s2[1001];
    fgets(s1, sizeof(s1), stdin);
    fgets(s2, sizeof(s2), stdin);
    
    s1[strcspn(s1, "\n")] = 0;
    s2[strcspn(s2, "\n")] = 0;
    
    bool result = solution(s1, s2);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each position can be swapped with multiple other positions, creating exponential states

⚠ Quadratic Growth

Space Complexity

O(2^n)

Need to store all visited states to avoid cycles

⚠ Quadratic Space

12.8K Views

Medium Frequency

~15 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler