Youtube
Given two strings s and t of length N, find the maximum number of possible matching pairs in strings s and t after swapping exactly two characters within s.
A swap is switching s[i] and s[j], where s[i] and s[j] denotes the character that is present at the ith and jth index of s, respectively. The matching pairs of the two strings are defined as the number of indices for which s[i] and t[i] are equal.
Note: This means you must swap two characters at different indices.
Test Cases
Example 1:
Input: s = "abcd" t = "adcb"
Output: 4
Explanation: Using 0-based indexing, and with i = 1 and j = 3, s[1] and s[3] can be swapped, making it "adcb".
Therefore, the number of matching pairs of s and t will be 4.
Output:
Input: s = "mno" t = "mno"
Output: 1
Explanation: Two indices have to be swapped, regardless of which two it is, only one letter will remain the same.
If i = 0 and j=1, s[0] and s[1] are swapped, making s = "nmo", which shares only "o" with t.
Solution
class Solution {
public int matchingPairs(String s, String t) {
// Write your code here
int match = 0;
Set<String> unmatched = new HashSet<>();
Set<Character> matched = new HashSet<>();
boolean hasDup = false;
int n = s.length();
for(int i=0; i<n; i++) {
if (s.charAt(i) == t.charAt(i)) {
match++;
if (matched.contains(s.charAt(i))) hasDup = true;
matched.add(s.charAt(i));
} else {
unmatched.add(s.charAt(i)+""+t.charAt(i));
}
}
if (match == n) return hasDup ? n : n-2;
if (match == n-1) {
String onlyUnmatched = (String)unmatched.toArray()[0];
if (hasDup || matched.contains(onlyUnmatched.charAt(0)) || matched.contains(onlyUnmatched.charAt(1))) {
return match;
}
return match - 1;
}
for(String um: unmatched) {
if (unmatched.contains(um.charAt(1)+""+um.charAt(0))) {
return match+2;
}
}
Set<Character> unmatchedS = new HashSet<>();
Set<Character> unmatchedT = new HashSet<>();
for(String um : unmatched) {
if(unmatchedS.contains(um.charAt(1)) || unmatchedT.contains(um.charAt(0))) {
return match + 1;
}
unmatchedS.add(um.charAt(0));
unmatchedT.add(um.charAt(1));
}
return match;
}
}