Greedy: String break problem

Problem Statement:

You are given 2 string and you need to check if some permutation of s1 can break s2 or vice-versa.
A string can break another string if s1[i] >= s2[i] for all i from 0 to n-1

Example

Input: s1 = “abc”, s2 = “xya”
Output: true

Because you can permute s2 = “ayx” that is able to break s1.

Solution

Solution is simple,
we sort both of the string and check if s1 can break s2 or s2 can break s1 and return the result.

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<unordered_map>

using namespace std;


bool breakString( string s1, string s2)
{
// O(n) time for comparision
  for ( int i=0; i<s1.size(); i++ ) 
      if ( s1[i]-'a' < s2[i]-'a') 
          return false;
  return true;
}
      
bool check_if_can_break(string s1, string s2) 
{
  sort(s1.begin(), s1.end()); 
  sort(s2.begin(), s2.end());
  return breakString(s1, s2) || breakString(s2, s1);
}

int main()
{
   string s1 = "abc";
   string s2 = "xya";

   if(check_if_can_break(s1, s2)){
      cout<<"String can break"<<endl;
   } else {
      cout<<"String cannot break"<<endl;

   }
    return 0;
}

Output:

String can break

 

 

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *