In this guide, you will get 854. K-Similar Strings LeetCode Solution with the best time and space complexity. The solution to K-Similar Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Strings s1 and s2 are k-similar (for some non-negative integer k) if we can swap the positions of two letters in s1 exactly k times so that the resulting string equals s2.
Given two anagrams s1 and s2, return the smallest k for which s1 and s2 are k-similar.
Example 1:
Input: s1 = “ab”, s2 = “ba”
Output: 1
Explanation: The two string are 1-similar because we can use one swap to change s1 to s2: “ab” –> “ba”.
Example 2:
Input: s1 = “abc”, s2 = “bca”
Output: 2
Explanation: The two strings are 2-similar because we can use two swaps to change s1 to s2: “abc” –> “bac” –> “bca”.
Constraints:
1 <= s1.length <= 20
s2.length == s1.length
s1 and s2 contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}.
s2 is an anagram of s1.
Complexity Analysis
Time Complexity: O(n^2k)
Space Complexity: O(n^2)
854. K-Similar Strings LeetCode Solution in C++
class Solution {
public:
int kSimilarity(string s1, string s2) {
queue<string> q{{s1}};
unordered_set<string> seen{{s1}};
for (int step = 0; !q.empty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
string curr = q.front();
q.pop();
if (curr == s2)
return step;
for (const string& child : getChildren(curr, s2)) {
if (seen.contains(child))
continue;
q.push(child);
seen.insert(child);
}
}
return -1;
}
private:
vector<string> getChildren(string& curr, const string& target) {
vector<string> children;
int i = 0; // the first index s.t. curr[i] != target[i]
while (curr[i] == target[i])
++i;
for (int j = i + 1; j < curr.length(); ++j)
if (curr[j] == target[i]) {
swap(curr[i], curr[j]);
children.push_back(curr);
swap(curr[i], curr[j]);
}
return children;
}
}; /* code provided by PROGIEZ */
854. K-Similar Strings LeetCode Solution in Java
class Solution {
public int kSimilarity(String s1, String s2) {
Queue<String> q = new ArrayDeque<>(List.of(s1));
Set<String> seen = new HashSet<>(Arrays.asList(s1));
for (int step = 0; !q.isEmpty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
final String curr = q.poll();
if (curr.equals(s2))
return step;
for (final String child : getChildren(curr, s2)) {
if (seen.contains(child))
continue;
q.offer(child);
seen.add(child);
}
}
return -1;
}
private List<String> getChildren(final String curr, final String target) {
List<String> children = new ArrayList<>();
char[] charArray = curr.toCharArray();
int i = 0; // the first index s.t. curr.charAt(i) != target.charAt(i)
while (curr.charAt(i) == target.charAt(i))
++i;
for (int j = i + 1; j < charArray.length; ++j)
if (curr.charAt(j) == target.charAt(i)) {
swap(charArray, i, j);
children.add(String.valueOf(charArray));
swap(charArray, i, j);
}
return children;
}
private void swap(char[] charArray, int i, int j) {
final char temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
}
} // code provided by PROGIEZ
854. K-Similar Strings LeetCode Solution in Python
class Solution:
def kSimilarity(self, s1: str, s2: str) -> int:
q = collections.deque([s1])
seen = {s1}
step = 0
while q:
for _ in range(len(q)):
curr = q.popleft()
if curr == s2:
return step
for child in self._getChildren(curr, s2):
if child in seen:
continue
q.append(child)
seen.add(child)
step += 1
return -1
def _getChildren(self, curr: str, target: str) -> list[str]:
children = []
s = list(curr)
i = 0 # the first index s.t. curr[i] != target[i]
while curr[i] == target[i]:
i += 1
for j in range(i + 1, len(s)):
if s[j] == target[i]:
s[i], s[j] = s[j], s[i]
children.append(''.join(s))
s[i], s[j] = s[j], s[i]
return children # code by PROGIEZ
