ఒక స్ట్రింగ్ మరొక స్ట్రింగ్ లీట్‌కోడ్ పరిష్కారాన్ని విచ్ఛిన్నం చేయగలదా అని తనిఖీ చేయండి


కఠినత స్థాయి మీడియం
ఓర్పు అత్యాశకరమైన సార్టింగ్ స్ట్రింగ్

సమస్యల నివేదిక

ఈ సమస్యలో మనకు రెండు ఇవ్వబడ్డాయి తీగలను s1 మరియు s2 ఒకే పరిమాణంతో. స్ట్రింగ్ s1 యొక్క కొన్ని ప్రస్తారణ స్ట్రింగ్ s2 యొక్క కొంత ప్రస్తారణను విచ్ఛిన్నం చేస్తుందో లేదో తనిఖీ చేయండి. మరో మాటలో చెప్పాలంటే, s2 s1 ను విచ్ఛిన్నం చేస్తుంది లేదా దీనికి విరుద్ధంగా ఉంటుంది.

0 మరియు n-1 మధ్య ఉన్న అన్ని i కోసం x [i]> = y [i] (అక్షర క్రమంలో) ఉంటే స్ట్రింగ్ x స్ట్రింగ్ y (పరిమాణం n రెండూ) ను విచ్ఛిన్నం చేస్తుంది.

ఉదాహరణ

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

వివరణ:

“ఐక్స్” అనేది s2 = ”xya” యొక్క ప్రస్తారణ, ఇది “abc” స్ట్రింగ్‌కు విచ్ఛిన్నం చేయగలదు, ఇది s1 = “abc” యొక్క ప్రస్తారణ.

s1 = "abe", s2 = "acd"
false

వివరణ:

S1 = ”abe” కోసం అన్ని ప్రస్తారణలు: “abe”, “aeb”, “bae”, “bea”, “eab” మరియు “eba” మరియు s2 = ”acd” కొరకు అన్ని ప్రస్తారణలు: “acd”, “adc ”,“ క్యాడ్ ”,“ సిడిఎ ”,“ డాక్ ”మరియు“ డికా ”. ఏదేమైనా, s1 నుండి ఎటువంటి ప్రస్తారణ లేదు, ఇది s2 నుండి కొంత ప్రస్తారణను విచ్ఛిన్నం చేస్తుంది మరియు దీనికి విరుద్ధంగా ఉంటుంది.

అప్రోచ్

ఈ సమస్యకు ఒక సరళమైన విధానం ఏమిటంటే, s1 యొక్క ప్రతి ప్రస్తారణను s2 యొక్క ప్రతి ప్రస్తారణతో తనిఖీ చేయడం, అవి పైన ఉన్న పరిస్థితిని సంతృప్తిపరిచే ఏదైనా జత ఉందో లేదో తెలుసుకోవడానికి. స్ట్రింగ్ పరిమాణం తక్కువగా ఉంటే మేము ఈ పని చేయవచ్చు. కానీ ఇక్కడ స్ట్రింగ్ యొక్క పొడవు చాలా పెద్దది కాబట్టి అన్ని ప్రస్తారణలను సృష్టించడం అసాధ్యం.

సమస్య స్టేట్‌మెంట్‌తో వెళుతున్నప్పుడు, ఒక స్ట్రింగ్ రెండవ స్ట్రింగ్‌ను పూర్తిగా కవర్ చేయాలని మేము కోరుకుంటున్నాము. ప్రతి అక్షర స్థానానికి, ఒక స్ట్రింగ్‌లోని అక్షరం రెండవ స్ట్రింగ్‌లోని అక్షరానికి సమానం కంటే ఎక్కువగా ఉండాలి (అక్షర క్రమం ప్రకారం). దీన్ని స్ట్రింగ్‌లోని అన్ని అక్షరాలు అనుసరించాలి.
ఇప్పుడు ఇక్కడ ప్రధాన పరిశీలన ఏమిటంటే, అన్ని స్ట్రింగ్ అక్షరాలు మొదటి స్ట్రింగ్‌లో సెకను కంటే ఎక్కువగా ఉండాలని కోరుకుంటే, అప్పుడు మేము s1 లోని చిన్న అక్షరాన్ని s2 లో చిన్న అక్షరాలతో పోల్చాలి. అదేవిధంగా గొప్పదానితో ఎక్కువ మూలకం. ఈ ప్రస్తారణ మరొకదాన్ని విచ్ఛిన్నం చేస్తుందో లేదో తనిఖీ చేయడానికి అనుకూలంగా ఉంటుంది. ఉదాహరణ s1 = ”abc” మరియు s2 = ”xya”. “Xya” ను క్రమబద్ధీకరించిన తరువాత అది ప్రతి పాయింట్ వద్ద “abc” కంటే ఎక్కువగా ఉంటుంది.

ఒక స్ట్రింగ్ మరొక స్ట్రింగ్ లీట్‌కోడ్ పరిష్కారాన్ని విచ్ఛిన్నం చేయగలదా అని తనిఖీ చేయండి

మేము అన్ని అక్షరాల కోసం s1 కన్నా s2 ను ఎక్కువ చేయగలిగితే, అప్పుడు మేము నిజమైనదిగా తిరిగి వస్తాము. రెండవ సందర్భంలో, మేము s2 కన్నా s1 ను ఎక్కువ చేయగలిగితే, అప్పుడు కూడా మేము తిరిగి వస్తాము. లేకపోతే ఎవరూ మరొకరు విచ్ఛిన్నం చేయలేరు.

అల్గోరిథం:

  • S1 యొక్క పొడవు s2 యొక్క పొడవుకు సమానం కాకపోతే, తప్పుడు తిరిగి ఇవ్వండి.
  • స్ట్రింగ్ రెండింటినీ ఆరోహణ లేదా అవరోహణ క్రమంలో క్రమబద్ధీకరించండి.
  • S1 అక్షరాలతో పాటు లూప్‌ను అమలు చేయండి. S1 [i]> = s2 [i] ఉంటే ప్రతి అక్షరానికి తనిఖీ చేయండి. అన్ని అక్షరాలు ఈ పరిస్థితిని సంతృప్తిపరిస్తే, తిరిగి నిజం.
  • ఇప్పుడు s2 అక్షరాలతో పాటు లూప్‌ను అమలు చేయండి. S2 [i]> = s1 [i] ఉంటే ప్రతి అక్షరానికి తనిఖీ చేయండి. అన్ని అక్షరాలు ఈ పరిస్థితిని సంతృప్తిపరిస్తే, తిరిగి నిజం.
  • లేకపోతే తిరిగి తప్పు.

అమలు

ఒక స్ట్రింగ్ మరొక స్ట్రింగ్ లీట్‌కోడ్ పరిష్కారాన్ని విచ్ఛిన్నం చేయగలిగితే చెక్ కోసం సి ++ ప్రోగ్రామ్

#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

ఒక స్ట్రింగ్ మరొక స్ట్రింగ్ లీట్‌కోడ్ పరిష్కారాన్ని విచ్ఛిన్నం చేయగలదా అని తనిఖీ చేయడానికి జావా ప్రోగ్రామ్

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

ఒక స్ట్రింగ్ మరొక స్ట్రింగ్ లీట్‌కోడ్ పరిష్కారాన్ని విచ్ఛిన్నం చేయగలదా అని తనిఖీ కోసం సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (nlog (n)): ఇక్కడ n అనేది ఇచ్చిన స్ట్రింగ్ యొక్క పొడవు. మేము ఇచ్చిన స్ట్రింగ్‌ను క్రమబద్ధీకరించాము మరియు దానిని రెండుసార్లు సరళంగా ప్రయాణించాము. అందువల్ల సమయ సంక్లిష్టత nlogn అవుతుంది.

అంతరిక్ష సంక్లిష్టత 

ఓ (1): మేము అదనపు మెమరీని ఉపయోగించలేదు. కొన్ని సార్టింగ్ అల్గోరిథంల కోసం స్థలం సంక్లిష్టత O (1) కంటే ఎక్కువగా ఉంటుంది.