Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/854.html

854. K-Similar Strings

Level

Hard

Description

Strings A and B are K-similar (for some non-negative integer K) if we can swap the positions of two letters in A exactly K times so that the resulting string equals B.

Given two anagrams A and B, return the smallest K for which A and B are K-similar.

Example 1:

Input: A = “ab”, B = “ba”

Output: 1

Example 2:

Input: A = “abc”, B = “bca”

Output: 2

Example 3:

Input: A = “abac”, B = “baca”

Output: 2

Example 4:

Input: A = “aabc”, B = “abca”

Output: 2

Note:

  1. 1 <= A.length == B.length <= 20
  2. A and B contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}

Solution

If A and B are the same, return 0.

Loop over A and B and only keep the letters that are different in the two strings. For example, if A = "aabc" and B = "abca", since the first letter 'a' is the same in A and B, it is not kept, so A and B become "abc" and "bca" respectively. After removing the same letters, all the letters need to be swapped, which can reduce the search space.

Then do breadth first search starting from A. For each string visited, which is str, obtain the first index where the letter in the string is different to the letter in B, which is startIndex. Then loop over all indices after startIndex and swap the letters at index i and index startIndex only if str.charAt(i) == B.charAt(startIndex). After swapping, add the new string to the queue for further search. Also maintain the number of swaps so far.

If at one step, the string equals B, then return the number of swaps.

  • class Solution {
    public int kSimilarity(String A, String B) {
        if (A.equals(B))
            return 0;
        int length = A.length();
        StringBuffer sbA = new StringBuffer();
        StringBuffer sbB = new StringBuffer();
        for (int i = 0; i < length; i++) {
            char cA = A.charAt(i), cB = B.charAt(i);
            if (cA != cB) {
                sbA.append(cA);
                sbB.append(cB);
            }
        }
        String strA = sbA.toString();
        String strB = sbB.toString();
        int swaps = 0;
        Set<String> set = new HashSet<String>();
        Queue<String> queue = new LinkedList<String>();
        queue.offer(strA);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String str = queue.poll();
                if (str.equals(strB))
                    return swaps;
                List<String> neighbors = getNeighbors(str, strB);
                for (String neighbor : neighbors) {
                    if (set.add(neighbor))
                        queue.offer(neighbor);
                }
            }
            swaps++;
        }
        return -1;
    }

    public List<String> getNeighbors(String str, String target) {
        int length = str.length();
        int startIndex = -1;
        for (int i = 0; i < length; i++) {
            if (str.charAt(i) != target.charAt(i)) {
                startIndex = i;
                break;
            }
        }
        List<String> neighbors = new ArrayList<String>();
        if (startIndex < 0)
            return neighbors;
        char[] array = str.toCharArray();
        char targetC = target.charAt(startIndex);
        for (int i = startIndex + 1; i < length; i++) {
            if (array[i] == targetC) {
                swap(array, startIndex, i);
                neighbors.add(new String(array));
                swap(array, startIndex, i);
            }
        }
        return neighbors;
    }

    public void swap(char[] array, int index1, int index2) {
        char temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
}

  • // OJ: https://leetcode.com/problems/k-similar-strings/
// Time: O(?)
// Space: O(?)
// Ref: https://leetcode.com/problems/k-similar-strings/discuss/151500/Logical-Thinking-with-Clear-Java-Code
class Solution {
public:
    int kSimilarity(string s, string t) {
        queue<string> q{ {s} };
        unordered_set<string> seen{ {s} };
        int step = 0;
        while (q.size()) {
            int cnt = q.size();
            while (cnt--) {
                auto u = q.front();
                q.pop();
                if (u == t) return step;
                int i = 0; // Get all possible neighbor strings
                while (i < s.size() && u[i] == t[i]) ++i; // find the first index that u[i] != t[i]
                for (int j = i + 1; j < s.size(); ++j) { // find a good swap index j such that u[j] == t[i]
                    if (u[j] == t[i]) {
                        swap(u[i], u[j]);
                        if (seen.count(u) == 0) {
                            seen.insert(u);
                            q.push(u);
                        }
                        swap(u[i], u[j]);
                    }
                }
            }
            ++step;
        }
        return -1;
    }
};

  • class Solution:
    def kSimilarity(self, s1: str, s2: str) -> int:
        def next(s):
            i = 0
            while s[i] == s2[i]:
                i += 1
            res = []
            for j in range(i + 1, n):
                if s[j] == s2[i] and s[j] != s2[j]:
                    res.append(s2[: i + 1] + s[i + 1 : j] + s[i] + s[j + 1 :])
            return res

        q = deque([s1])
        vis = {s1}
        ans, n = 0, len(s1)
        while 1:
            for _ in range(len(q)):
                s = q.popleft()
                if s == s2:
                    return ans
                for nxt in next(s):
                    if nxt not in vis:
                        vis.add(nxt)
                        q.append(nxt)
            ans += 1



  • func kSimilarity(s1 string, s2 string) int {
	next := func(s string) []string {
		i := 0
		res := []string{}
		for ; s[i] == s2[i]; i++ {
		}
		for j := i + 1; j < len(s1); j++ {
			if s[j] == s2[i] && s[j] != s2[j] {
				res = append(res, s[:i]+string(s[j])+s[i+1:j]+string(s[i])+s[j+1:])
			}
		}
		return res
	}

	q := []string{s1}
	vis := map[string]bool{s1: true}
	ans := 0
	for {
		for i := len(q); i > 0; i-- {
			s := q[0]
			q = q[1:]
			if s == s2 {
				return ans
			}
			for _, nxt := range next(s) {
				if !vis[nxt] {
					vis[nxt] = true
					q = append(q, nxt)
				}
			}
		}
		ans++
	}
}

All Problems

All Solutions