Check If a String Can Break Another String
Given two strings: s1
and s2
with the same size, check if some permutation of string s1
can break some permutation of string s2
or vice-versa (in other words s2
can break s1
).
A string x
can break string y
(both of size n
) if x[i] >= y[i]
(in alphabetical order) for all i
between 0
and n-1
.
Example 1:
Input: s1 = "abc", s2 = "xya"
Output: true
Explanation: "ayx" is a permutation of s2="xya" which can break to string "abc" which is a permutation of s1="abc".
Example 2:
Input: s1 = "abe", s2 = "acd"
Output: false
Explanation: All permutations for s1="abe" are: "abe", "aeb", "bae", "bea", "eab" and "eba" and all permutation for s2="acd" are: "acd", "adc", "cad", "cda", "dac" and "dca". However, there is not any permutation from s1 which can break some permutation from s2 and vice-versa.
Example 3:
Input: s1 = "leetcodee", s2 = "interview"
Output: true
Constraints:
s1.length == n
s2.length == n
1 <= n <= 10^5
All strings consist of lowercase English letters.
// Smaller Code
class Solution {
public boolean checkIfCanBreak(String s1, String s2) {
int n = s1.length();
int[] str1 = new int[26], str2 = new int[26];
for (int i = 0; i < n; i++)
str1[s1.charAt(i) - 97]++;
for (int i = 0; i < n; i++)
str2[s2.charAt(i) - 97]++;
int count1 = 0, count2 = 0;
boolean f1 = false, f2 = false;
for (int i = 0; i < 26; i++) {
count1 += str1[i];
count2 += str2[i];
if (count1 > count2) {
// If a string starts dominationg then it cannot reverse in between
if (f2)
return false;
f1 = true;
} else if (count2 > count1) {
if (f1)
return false;
f2 = true;
}
}
return true;
}
}
// My own Solution
class Solution {
public boolean checkIfCanBreak(String s1, String s2) {
return helper(s1, s2) || helper(s2, s1);
}
public boolean helper(String s1, String s2) {
int[] str1 = new int[26];
int[] str2 = new int[26];
for (char c : s1.toCharArray())
str1[c - 'a']++;
for (char c : s2.toCharArray())
str2[c - 'a']++;
int p1 = 0, p2 = 0;
while (p1 < 26 && p2 < 26) {
while (p1 < 26 && str1[p1] == 0)
p1++;
while (p2 < 26 && str2[p2] == 0)
p2++;
if (p1 == 26 && p2 == 26)
break;
if (p2 < p1)
return false;
else {
if (str1[p1] == str2[p2]) {
str1[p1] = 0;
str2[p2] = 0;
p1++;
p2++;
} else if (str1[p1] > str2[p2]) {
str1[p1] -= str2[p2];
p2++;
} else {
str2[p2] -= str1[p1];
p1++;
}
}
}
return true;
}
}
Last updated