Swap Characters Once to Minimize Differences - Google Top Interview Questions


Problem Statement :


You are given two lowercase alphabet strings s and t of the same length.

Given that you can make at most one swap between two characters in s, return the minimum number of indices where s[i] ≠ t[i].

Constraints

1 ≤ n ≤ 100,000 where n is the length of s and t

Example 1

Input

s = "abbz"

t = "zcca"

Output

2

Explanation

We can swap "a" and "z" to turn s into "zbba". Then there's 2 characters that differ between t.


Example 2

Input
s = "zfba"

t = "zbca"

Output

1

Explanation

We can swap "f" and "b" to turn s into "zbfa". Then there's only 1 character that differ between t.



Example 3

Input

s = "abc"

t = "abc"

Output

0

Explanation

We don't need to swap since all the characters in s already match with t.



Solution :



title-img




                        Solution in C++ :

const int Z = 26;

int mismatched[Z];

int solve(string s, string t) {
    memset(mismatched, 0, sizeof(mismatched));
    int mismatched_pairs = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        mismatched_pairs += s[i] != t[i];
        if (s[i] != t[i]) mismatched[s[i] - 'a'] |= 1 << (t[i] - 'a');
    }

    bool can_swap_one = false;
    for (int i = 0; i < Z; i++) {
        if (!mismatched[i]) continue;
        int i_bit = 1 << i;
        for (int j = 0; j < Z; j++) {
            if ((mismatched[i] & (1 << j)) && (mismatched[j] & i_bit)) return mismatched_pairs - 2;
            can_swap_one |= mismatched[j] & i_bit;
        }
    }

    return mismatched_pairs - can_swap_one;
}
                    


                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(String a, String b) {
        int N = a.length();
        boolean[][] occ = new boolean[26][26];
        int ans = 0;
        boolean[] inA = new boolean[26];
        boolean[] inB = new boolean[26];
        for (int i = 0; i < N; i++) {
            int v1 = a.charAt(i) - 'a';
            int v2 = b.charAt(i) - 'a';
            if (v1 != v2) {
                ans++;
                occ[v1][v2] = true;
                inA[v1] = true;
                inB[v2] = true;
            }
        }
        for (int i = 0; i < 26; i++) {
            for (int j = i + 1; j < 26; j++) {
                if (occ[i][j] && occ[j][i]) {
                    // there exists indices where letters i and j can be swapped.
                    return ans - 2;
                }
            }
        }

        for (int i = 0; i < 26; i++) {
            if (inA[i] && inB[i]) {
                // a swap exists to get a pair of letter i.
                return ans - 1;
            }
        }

        return ans;
    }
}
                    


                        Solution in Python : 
                            
class Solution:
    def solve(self, s, t):
        badpairs = set()
        ans = 0
        for (a, b) in zip(s, t):
            if a == b:
                continue
            badpairs.add((a, b))
            ans += 1
        for x, y in badpairs:
            if (y, x) in badpairs:
                return ans - 2
        for x, _ in badpairs:
            for ch in ascii_lowercase:
                if (ch, x) in badpairs:
                    return ans - 1
        return ans
                    


View More Similar Problems

Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

View Solution →

Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

View Solution →

Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func

View Solution →

Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

View Solution →

Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

View Solution →

Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F

View Solution →