Apply Bitwise Operations To Make Strings Equal - Leetcode Solution

Problem Statement:

Given two strings a and b, return true if you can swap two letters in a so the result is equal to b, otherwise, return false.

Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at a[i] and a[j]. For example, swapping at indices 0 and 2 in "abcd" results in "cbad".

Example 1: Input: a = "ab", b = "ba" Output: true Explanation: You can swap a[0] = 'a' and a[1] = 'b' to get "ba", which is equal to b.

Example 2: Input: a = "ab", b = "ab" Output: false Explanation: The only letters you can swap are a[0] = 'a' and a[1] = 'b', which results in "ba" != b.

Example 3: Input: a = "aa", b = "aa" Output: true Explanation: You can swap a[0] = 'a' and a[1] = 'a' to get "aa", which is equal to b.

Example 4: Input: a = "aaaaaaabc", b = "aaaaaaacb" Output: true

Example 5: Input: a = "", b = "" Output: true

Approach:

• If the strings have different lengths, it is impossible to make them equal by swapping two letters and we can return false. Otherwise, we can use bit operations to check if it is possible to make the two strings equal by swapping two letters.
• We can use two bitmaps (a_bitmap and b_bitmap) to represent the set of characters in each string. For each character in a, we can set the corresponding bit in a_bitmap to 1. Similarly, for each character in b, we can set the corresponding bit in b_bitmap to 1.
• We can check if the two bitmaps are equal. If they are not, we return false because it means that the two strings have different sets of characters and it is impossible to make them equal by swapping two letters. Otherwise, we can check how many positions differ between a and b.
• If there are exactly two positions that differ, we can swap the characters at those positions in a and check if the resulting string is equal to b. If it is, we can return true. Otherwise, we return false.

Solution:

class Solution { public: bool areAlmostEqual(string a, string b) { if (a.length() != b.length()) { return false; } int n = a.length(); int a_bitmap = 0; int b_bitmap = 0; int diff_count = 0; int first_diff_pos = -1; int second_diff_pos = -1; for (int i = 0; i < n; i++) { if (a[i] != b[i]) { diff_count++; if (diff_count == 1) { first_diff_pos = i; } else if (diff_count == 2) { second_diff_pos = i; } } a_bitmap |= (1 << (a[i] - 'a')); b_bitmap |= (1 << (b[i] - 'a')); } if (diff_count == 0) { return true; } else if (diff_count == 2) { swap(a[first_diff_pos], a[second_diff_pos]); return (a == b); } else { return false; } } };

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the strings a and b. The for loop iterates over the strings once, and the bitwise operations and string comparison take constant time.

Space Complexity:

The space complexity of this solution is O(1) because we use only a constant amount of space to store the bitmaps and other variables.

1