Practice Projects

Check if One String Swap Can Make Strings Equal

Problem Statement

  • aapko do strings diye gaye hain, s1 aur s2, jo ek hi length ke hain. Ek string swap ka operation hota hai jab aap string ke do indices (zaroori nahi ki different ho) chunte hain aur un indices par characters ko swap karte hain.

    Aapko yeh check karna hai ki kya yeh possible hai ki sirf ek string par at most ek string swap karke dono strings ko equal banaya ja sake. Agar yeh possible hai, toh return true, warna return false.

    Example 1:

    Input: s1 = “bank”, s2 = “kanb”

    Output: true

    Explanation: For example, s2 ke first character ko last character se swap karke “bank” banate hain.

    Example 2:

    Input: s1 = “attack”, s2 = “defend”

    Output: false

    Explanation: Ek string swap karke inhe equal banana impossible hai.

    Example 3:

    Input: s1 = “kelb”, s2 = “kelb”

    Output: true

    Explanation: Yeh do strings pehle se hi equal hain, isliye koi string swap operation ki zaroorat nahi.

    Constraints:

    1. s1 ki length aur s2 ki length 1 se 100 ke beech ho.

    2. s1 aur s2 ki length barabar ho.

    3. s1 aur s2 sirf lowercase English letters ka istemal karte ho.

Practice Projects

Check if One String Swap Can Make Strings Equal

humein yeh dekhna hai ki kya do strings ko at most ek swap se equal banaya ja sakta hai ya nahi, aur iska logic kuch is tarah hai:

0 mismatches: Agar dono strings pehle se hi same hain, toh unhe change karne ki koi zaroorat nahi. Already equal hain. ✅

1 mismatch: Agar sirf ek hi mismatch hai, toh ek swap se inhe fix karna possible nahi hai. Ek mismatch fix karne ke liye kam se kam do positions hone chahiye.

2 mismatches: Agar do mismatches hain, toh hum unhe swap kar sakte hain aur check kar sakte hain ki kya swap ke baad strings equal ban jaati hain.

More than 2 mismatches: Agar do se zyada mismatches hain, toh immediately return false kyunki ek hi swap se inhe equal banana possible nahi hoga.

Intuition

Identify mismatches: Pehle, humein dono strings s1 aur s2 ko character by character compare karna hai aur mismatches identify karne hain. In mismatches ko track karna important hai.

Check number of mismatches: Phir, humein mismatches ki count karni hai:

0 mismatches: Agar koi mismatch nahi hai, toh strings already equal hain. Return true.

1 mismatch: Agar sirf ek mismatch hai, toh ek swap se strings ko equal banana possible nahi hai. Return false.

2 mismatches: Agar do mismatches hain, toh humein in mismatched positions ko swap karne ki koshish karni chahiye aur check karna hai ki swap ke baad strings equal hain ya nahi. Agar equal hain, toh return true, warna return false.

More than 2 mismatches: Agar do se zyada mismatches hain, toh ek swap se inhe equal banana possible nahi hai. Return false.

Swap and check: Agar 2 mismatches hain, toh in positions par characters ko swap karke check karo ki kya strings equal ho jaati hain. Agar equal ho jaati hain, toh return true, warna return false.

Approach

Time Complexity

  1. Identify mismatches: Humein s1 aur s2 ko character by character compare karna hoga. Yeh comparison O(n) time complexity leta hai, jahan n strings ki length hai.

  2. Check number of mismatches: Mismatches count karna bhi O(n) time complexity leta hai.

  3. Swap and check: Agar 2 mismatches hain, toh unhe swap karke check karne ka kaam constant time (O(1)) mein hota hai.

Toh overall time complexity hogi O(n) + O(n) + O(1) = O(n).

Space Complexity

  1. Identify mismatches: Humein mismatched positions ko store karna hoga. Worst case mein, humein array of size 2 use karna hoga mismatches store karne ke liye, jo O(1) space complexity leta hai.

  2. Check number of mismatches aur swap: Yeh dono steps bhi constant space mein hote hain (O(1)).

 

Solution

				
					var areAlmostEqual = function(s1, s2) {
    // s1 ko array mein convert karte hain
    let arr = [...s1], x = -1; // x variable -1 se initialize karte hain

    // s1 ke har character ko compare karte hain s2 ke corresponding character se
    for (let i = 0; i < s1.length; i++) {
        if (arr[i] !== s2[i]) { // agar characters match nahi karte
            if (x === -1) x = i; // agar pehla mismatch hai, x ko current index pe set karte hain
            else {
                // agar dusra mismatch hai, to swap karte hain characters
                [arr[i], arr[x]] = [arr[x], arr[i]];
                
                // swap ke baad check karte hain ki arr s2 ke barabar hai ya nahi
                return arr.join('') === s2;
            }
        }
    }
    
    // agar koi mismatch nahi mila, to check karte hain ki s1 aur s2 already equal hain
    return s1 === s2;
};

  • Initialization:

    • Pehle, s1 ko ek array mein convert karte hain (arr = [...s1]) taaki hum isse easily characters ko swap kar sakein.

    • x variable ko -1 se initialize karte hain. Yeh variable pehle mismatch index ko track karne ke liye use hota hai.

  • Character Comparison:

    • Loop ke through, hum s1 ke har character ko s2 ke corresponding character se compare karte hain.

    • Agar characters match nahi karte (arr[i] !== s2[i]), toh do cases ho sakte hain:

      • Pehla mismatch: Agar x ab tak -1 hai, toh yeh pehla mismatch hai. Hum x ko current index i pe set kar dete hain.

      • Dusra mismatch: Agar x already set hai, toh yeh dusra mismatch hai. Hum arr[i] aur arr[x] ko swap karte hain. Swap karne ke baad, arr ko string mein convert karte hain aur check karte hain ki kya arr aur s2 same hain (arr.join('') === s2).

  • Final Check:

    • Agar loop ke baad koi mismatch nahi mila, toh hum direct check karte hain ki kya s1 aur s2 already equal hain (s1 === s2

Solution

				
					class Solution {
public:
    bool areAlmostEqual(string s1, string s2) {
        int x = -1; // x ko -1 se initialize karte hain, jo pehle mismatch index ko track karega
        
        // s1 ke har character ko s2 ke corresponding character se compare karte hain
        for (int i = 0; i < s1.size(); i++) {
            if (s1[i] != s2[i]) { // agar characters match nahi karte
                if (x == -1) {
                    x = i; // agar pehla mismatch hai, x ko current index pe set karte hain
                } else {
                    // agar dusra mismatch hai, to swap karte hain characters ko
                    swap(s1[i], s1[x]);
                    
                    // swap ke baad check karte hain ki kya s1 aur s2 equal hain
                    return s1 == s2;
                }
            }
        }
        
        // agar koi mismatch nahi mila, to check karte hain ki kya s1 aur s2 already equal hain
        return s1 == s2;
    }
};

      • Initialization: int x = -1; – yeh variable pehle mismatch index ko track karne ke liye use hota hai.

      • Character Comparison:

        • for (int i = 0; i < s1.size(); i++) { – loop ke through, hum s1 ke har character ko s2 ke corresponding character se compare karte hain.

        • if (s1[i] != s2[i]) { – agar characters match nahi karte hain, toh do cases ho sakte hain:

          • if (x == -1) x = i; – agar pehla mismatch hai, x ko current index i pe set karte hain.

          • else { swap(s1[i], s1[x]); return s1 == s2; } – agar dusra mismatch hai, toh s1[i] aur s1[x] ko swap karte hain aur swap ke baad check karte hain ki kya s1 aur s2 equal hain.

      • Final Check:

        • return s1 == s2; – agar loop ke baad koi mismatch nahi mila, toh check karte hain ki kya s1 aur s2 already equal hain.