1433. Check If a String Can Break Another String LeetCode Solution

In this guide, you will get 1433. Check If a String Can Break Another String LeetCode Solution with the best time and space complexity. The solution to Check If a String Can Break Another String 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.

Problem Statement
Complexity Analysis
Check If a String Can Break Another String solution in C++
Check If a String Can Break Another String solution in Java
Check If a String Can Break Another String solution in Python
Additional Resources

1433. Check If a String Can Break Another String LeetCode Solution image

Problem Statement of 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 or vice-versa.
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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(26) = O(1)

1433. Check If a String Can Break Another String LeetCode Solution in C++

class Solution {
 public:
  bool checkIfCanBreak(string s1, string s2) {
    vector<int> count1(26);
    vector<int> count2(26);

    for (const char c : s1)
      ++count1[c - 'a'];

    for (const char c : s2)
      ++count2[c - 'a'];

    return canBreak(count1, count2) || canBreak(count2, count1);
  }

 private:
  // Returns true if count1 can break count2.
  bool canBreak(const vector<int>& count1, const vector<int>& count2) {
    int diff = 0;
    for (int i = 0; i < 26; ++i) {
      diff += count2[i] - count1[i];
      // count2 is alphabetically greater than count1.
      if (diff < 0)
        return false;
    }
    return true;
  }
};
/* code provided by PROGIEZ */

1433. Check If a String Can Break Another String LeetCode Solution in Java

class Solution {
  public boolean checkIfCanBreak(String s1, String s2) {
    int[] count1 = new int[26];
    int[] count2 = new int[26];

    for (final char c : s1.toCharArray())
      ++count1[c - 'a'];

    for (final char c : s2.toCharArray())
      ++count2[c - 'a'];

    return canBreak(count1, count2) || canBreak(count2, count1);
  }

  // Returns true if count1 can break count2.
  private boolean canBreak(int[] count1, int[] count2) {
    int diff = 0;
    for (int i = 0; i < 26; ++i) {
      diff += count2[i] - count1[i];
      // count2 is alphabetically greater than count1.
      if (diff < 0)
        return false;
    }
    return true;
  }
}
// code provided by PROGIEZ

1433. Check If a String Can Break Another String LeetCode Solution in Python

class Solution:
  def checkIfCanBreak(self, s1: str, s2: str) -> bool:
    count1 = collections.Counter(s1)
    count2 = collections.Counter(s2)

    def canBreak(count1: dict[str, int], count2: dict[str, int]) -> bool:
      """Returns True if count1 can break count2."""
      diff = 0
      for c in string.ascii_lowercase:
        diff += count2[c] - count1[c]
        # count2 is alphabetically greater than count1.
        if diff < 0:
          return False
      return True

    return canBreak(count1, count2) or canBreak(count2, count1)
 # code by PROGIEZ