Welcome to Subscribe On Youtube

854. K-Similar Strings

Description

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.

Solutions

BFS.

• Java
• C++
• Python
• Go

• class Solution {
      public int kSimilarity(String s1, String s2) {
          Deque<String> q = new ArrayDeque<>();
          Set<String> vis = new HashSet<>();
          q.offer(s1);
          vis.add(s1);
          int ans = 0;
          while (true) {
              for (int i = q.size(); i > 0; --i) {
                  String s = q.pollFirst();
                  if (s.equals(s2)) {
                      return ans;
                  }
                  for (String nxt : next(s, s2)) {
                      if (!vis.contains(nxt)) {
                          vis.add(nxt);
                          q.offer(nxt);
                      }
                  }
              }
              ++ans;
          }
      }
  
      private List<String> next(String s, String s2) {
          int i = 0, n = s.length();
          char[] cs = s.toCharArray();
          for (; cs[i] == s2.charAt(i); ++i) {
          }
  
          List<String> res = new ArrayList<>();
          for (int j = i + 1; j < n; ++j) {
              if (cs[j] == s2.charAt(i) && cs[j] != s2.charAt(j)) {
                  swap(cs, i, j);
                  res.add(new String(cs));
                  swap(cs, i, j);
              }
          }
          return res;
      }
  
      private void swap(char[] cs, int i, int j) {
          char t = cs[i];
          cs[i] = cs[j];
          cs[j] = t;
      }
  }
  

• class Solution {
  public:
      int kSimilarity(string s1, string s2) {
          queue<string> q{ {s1} };
          unordered_set<string> vis{ {s1} };
          int ans = 0;
          while (1) {
              for (int i = q.size(); i; --i) {
                  auto s = q.front();
                  q.pop();
                  if (s == s2) {
                      return ans;
                  }
                  for (auto& nxt : next(s, s2)) {
                      if (!vis.count(nxt)) {
                          vis.insert(nxt);
                          q.push(nxt);
                      }
                  }
              }
              ++ans;
          }
      }
  
      vector<string> next(string& s, string& s2) {
          int i = 0, n = s.size();
          for (; s[i] == s2[i]; ++i) {}
          vector<string> res;
          for (int j = i + 1; j < n; ++j) {
              if (s[j] == s2[i] && s[j] != s2[j]) {
                  swap(s[i], s[j]);
                  res.push_back(s);
                  swap(s[i], s[j]);
              }
          }
          return res;
      }
  };
  

• 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