Check If a String Can Break Another String Leetcode Solution

Difficulty Level Medium
algorithms coding endurance Greedy Interview interviewprep LeetCode LeetCodeSolutions Sorting StringViews 1840

Problem Statement

In this problem we are 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

s1 = "abc", s2 = "xya"
true

Explanation:

“ayx” is a permutation of s2=”xya” which can break to string “abc” which is a permutation of s1=”abc”.

s1 = "abe", s2 = "acd"
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.

Approach

A simple approach to this problem is to check each permutation of s1 with each permutation of s2 to find if their exist any pair that satisfy above condition. We can do this thing if the size of the string is small. But here length of the string is very large so it is impossible to create all permutations.

Going with the problem statement we want one string to completely cover the second string. Covering in sense that for each character position, the character at one string should be greater than equal to character at the second string( according to alphabetical order). This should be followed by all the characters in string.
Now the main observation here is if we want all the string characters to be greater in first string than second then we have to compare smaller character in s1 with smaller character in s2. Similarly greater element with greater one. This permutation will be optimum to check if one breaks another or not. Example s1=”abc” and s2=”xya”. After sorting “xya” it will be higher than “abc” at each point.

Check If a String Can Break Another String Leetcode Solution

If we able to make s1 greater than s2 for all characters then we return true. In second case if we able to make s2 greater than s1 then also we return true. Otherwise no one can break other.

Algorithm:

  • If length of s1 is not equal to length of s2 then return false.
  • Sort both the string in ascending or descending order.
  • Run a loop along the characters of s1. Check for each character if s1[i]>=s2[i]. If all the  characters satisfy this condition then return true.
  • Now run a loop along the characters of s2. Check for each character if s2[i]>=s1[i]. If all the characters satisfy this condition then return true.
  • Else return false.

Implementation

C++ Program for Check If a String Can Break Another String Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

bool checkIfCanBreak(string s1, string s2)
{
    if(s1.length() != s2.length()) return false;

    sort(s1.begin(),s1.end());
    sort(s2.begin(),s2.end());

    int i=0;
    while(s1[i])
    {
        if(s1[i]<s2[i]) break;
        i++;
    }

    if(i==s1.length()) return true;

    i=0;
    while(s2[i])
    {
        if(s1[i]>s2[i]) break;
        i++;
    }

    if(i==s2.length()) return true;

    return false;
}

int main() 
{
    string s1 = "abc";
    string s2 = "xya";
    if( checkIfCanBreak( s1, s2) )
        cout<< "true" ;
    else
        cout<< "false";
    return 0; 
}

true

Java Program for Check If a String Can Break Another String Leetcode Solution

import java.util.*;
class Rextester{
    
    public static boolean checkIfCanBreak(String s1, String s2) 
    {    
        if(s1.length() != s2.length()) return false;
        
        char[] c1=s1.toCharArray();
        char[] c2=s2.toCharArray();
        Arrays.sort(c1);
        Arrays.sort(c2);
        
        int i=0;
        while(i<s1.length())
        {
            if(c1[i]<c2[i]) break;
            i++;
        }
        
        if(i==s1.length()) return true;
        
        i=0;
        while(i<s2.length())
        {
            if(c1[i]>c2[i]) break;
            i++;
        }
        
        if(i==s2.length()) return true;
        
        return false;        
    }
    
    public static void main(String args[])
    {
        String s1 = "abc";
        String s2 = "xya";
        System.out.println(checkIfCanBreak( s1, s2) );
    }
}

true

Complexity Analysis for Check If a String Can Break Another String Leetcode Solution

Time Complexity

O(nlog(n)) : where n is the length of the given string. We sorted the given string and traversed it two times linearly. Hence time complexity will be nlogn.

Space Complexity 

O(1) : we did not used any extra memory. Although for some sorting algorithms space complexity can be greater than O(1).

Translate »