STRCOMPARE - Editorial

taran_1407 · November 21, 2021, 2:37pm

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Manan Bordia and Lavish Gupta
Tester: Abhinav Sharma
Editorialist: Taranpreet Singh

DIFFICULTY

Simple

PREREQUISITES

None

PROBLEM

Given two strings A and B of length N each. Find the number of indices i such that A[i\ldots N] \lt B[i \ldots N].

QUICK EXPLANATION

If A_i \lt B_i, then index i is good. If A_i \gt B_i, then index is not good.
If A_i = B_i, then index i is good if and only if index i+1 is good.

EXPLANATION

Let’s call an index i good if A[i\ldots N] \lt B[i \ldots N] holds.

Let us solve this problem for the easier cases first. Whenever we have A_i \neq B_i, we can immediately decide for index i whether it is good or not.

What happens when A_i = B_i? We’d need to compare A_{i+1} and B_{i+1} and so on, to find the first position p where A_p \neq B_p. All indices from i to p are decided by whether A_p \lt B_p is true or not.

We can see that if A_i = B_i, then index i is good only if index i+1 is good. Let’s compute this from right to left. Maintain whether index i+1 is good or not. First check if A_i \neq B_i. If yes, check if index is good or not by comparing A_i and B_i.

Maintain a count of good indices.

nextGood = false # Whether index i+1 is good or not
count = 0
for i in N-1 to 0:
    if A[i] == B[i]:
        if nextGood: count++
    else:
        if A[i] < B[i]:
            count++
            nextGood = true
        else:
            nextGood = false

print count

TIME COMPLEXITY

The time complexity is O(N) per test case.

SOLUTIONS

Setter's Solution

#include <bits/stdc++.h>
using namespace std;
 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        assert('a'<=g and g<='z');
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 100000;
const int MAX_LEN = 1000000;
const int MAX_SUM_LEN = 1000000;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
int sum_len = 0;
int max_n = 0;
int max_k = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
 
int n,k;
string s;

 
void solve()
{

    n = readIntLn(1, MAX_LEN);
    string a = readStringLn(1, MAX_LEN);
    string b = readStringLn(1, MAX_LEN);

    sum_len += n;

    assert(a.length()==n && b.length()==n);
    for(int i = 0 ; i < n ; i++)
    {
        int val_a = a[i] - 'a' ;
        int val_b = b[i] - 'a' ;
        assert(val_a >= 0 && val_a < 26) ;
        assert(val_b >= 0 && val_b < 26) ;
    }

    int ans = 0;

    if(a == b)
    {
        cout << ans << '\n' ;
        return ;
    }

    for(int i = 0 ; i < n ; i++)
    {
        int flag = 0 ;
        for(int j = i ; j < n ; j++)
        {
            if(a[j] < b[j])
            {
                ans += (j-i+1) ;
                i = j ;
                break ;
            }
            if(a[j] > b[j])
            {
                i = j ;
                break ;
            }
            if(j == n-1)
                flag = 1 ;
        }
        if(flag)
            break ;
    }

    cout<<ans<<'\n';
}
 
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w" , stdout);
    #endif
    // fast;

    int t = 1;
    
    t = readIntLn(1,MAX_T);
    
    for(int i=1;i<=t;i++)
    {     
       solve();
    }
    
    assert(sum_len <= MAX_SUM_LEN);
    assert(getchar() == -1);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    // cerr<<"maxN : " << max_n << '\n';
    // cerr<<"maxK : " << max_k << '\n';
    cerr<<"Sum of lengths : " << sum_len << '\n';
    // cerr<<"Maximum length : " << max_n << '\n';
    // cerr<<"Total operations : " << total_ops << '\n';
    // cerr<<"Answered yes : " << yess << '\n';
    // cerr<<"Answered no : " << nos << '\n';
}

Tester's Solution

#include <bits/stdc++.h>
using namespace std;
 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        assert('a'<=g and g<='z');
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 100000;
const int MAX_LEN = 1e6;
const int MAX_SUM_LEN = 1e6;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
int sum_len = 0;
int max_n = 0;
int max_k = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
 
int n,k;
string s;

 
void solve()
{

    n = readIntLn(1, 1e6);
    string a = readStringLn(1, MAX_LEN);
    string b = readStringLn(1, MAX_LEN);

    sum_len += n;

    assert(a.length()==n && b.length()==n);

    int ans = 0;

    int f=0;
    for(int i=n-1; i>=0; i--){
        if(a[i]<b[i]){
            if(!f) f=1;
        }
        else if(a[i]>b[i]){
            if(f) f=0;
        }

        ans+=f;
    }

    cout<<ans<<'\n';


}
 
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w" , stdout);
    #endif
    fast;

    int t = 1;
    
    t = readIntLn(1,MAX_T);
    
    for(int i=1;i<=t;i++)
    {     
       solve();
    }
    
    assert(sum_len <= MAX_SUM_LEN);
    assert(getchar() == -1);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    // cerr<<"maxN : " << max_n << '\n';
    // cerr<<"maxK : " << max_k << '\n';
    cerr<<"Sum of lengths : " << sum_len << '\n';
    // cerr<<"Maximum length : " << max_n << '\n';
    // cerr<<"Total operations : " << total_ops << '\n';
    // cerr<<"Answered yes : " << yess << '\n';
    // cerr<<"Answered no : " << nos << '\n';
}

Editorialist's Solution

import java.util.*;
import java.io.*;
class STRCOMPARE{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        String A = n(), B = n();
        int ans = 0;
        boolean small = false;
        for(int i = N-1; i>= 0; i--){
            if(A.charAt(i) < B.charAt(i)){
                ans++;
                small = true;
            }else if(A.charAt(i) == B.charAt(i)){
                if(small)
                    ans++;
            }else small = false;
        }
        pn(ans);
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new STRCOMPARE().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always.

runtimeterror5 · November 22, 2021, 8:28pm

package com.company;
import java.util.*;

public class Q1 {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int N;
int T = sc.nextInt();
while (T-- != 0) {
int c = 0;
N = sc.nextInt();
String A = sc.nextLine();
String B = sc.nextLine();
for (int i = 0; i < A.length(); i++) {
String str1=A.substring(i);
String str2=B.substring(i)
if (str1.compareTo(str2) < 0)
++c;
}
System.out.println(c);
}
}
}

please somebody tell me the problem in this logic and code…
This is giving NZEC error in codechef ide and also some other error in my offline ide…
The code runs fine when I remove the T and N statements…Please help me,Ive just started Java and DSA and I am stuck on this…

package com.company;
import java.util.*;

public class Q1 {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int c = 0;
String A = sc.nextLine();
String B = sc.nextLine();
for (int i = 0; i < A.length(); i++) {
String str1=A.substring(i);
String str2=B.substring(i)
if (str1.compareTo(str2) < 0)
++c;
}
System.out.println(c);
}
}

kavyaa2002 · November 23, 2021, 5:22am

#include
#include <string.h>
using namespace std;

int main()
{
int t;
cin >> t;
while(t–)
{
int n;
cin >> n;

    string a, b;
    cin >> a;
    cin >> b;
    
    int y = 0;
    for(int i = 0 ; i < n ; i++)
    {
       string a_s = a.substr(i , n - i);
       string b_s = b.substr(i , n - i);
       
       if(a_s < b_s)
       {
           y++;
       }
    } 
    cout << y << endl;
}
return 0;

}

What is the time complexity of this code?
This ended up as TLE.

satyamm97 · November 23, 2021, 6:21am

Its O(n^2) since substr is O(n) operation in worst case.

resilient_nik9 · November 23, 2021, 6:29am

You can verify it here – Standard Template Library | HackerEarth

ssvb · November 23, 2021, 6:42am

The time complexity of your code is O(N^2) for two different reasons:

each substr is creating a new string, which means O(N) time complexity just to copy characters into it one by one (plus some extra memory allocation overhead)
comparing two strings has O(N) time complexity in the worst case (if both strings are equal)

The substr part of the performance problem can be fixed by using std::string_view. But the string comparison problem can’t be fixed without changing the algorithm to do something similar to what is described in the editorial.

The worst testcase is T=1, N=10^6 and two “aaaa … aaaaa” strings consisting of just “a” character to compare.

divyansh_08 · November 23, 2021, 7:32am

.substr() takes O(n) time complexity in the worst case, and you are running it for every i, hence O(n*n)

kishan2402 · November 23, 2021, 7:32am

hello, can anyone tell me what is wrong in this code
Thanks in advance

#include <bits/stdc++.h>
#define ll long long int
#define fastio ios_base::sync_with_stdio(false): cin.tie(NULL);
using namespace std;

ll lim=1e9+7;

ll power(ll a,ll b,ll lim)
{
    ll res=1;
    while(b)
    {
        if(b&1)
            res=(res*a)%lim;
        a=(a*a)%lim;
        b/=2;
    }
    return res;
}

void solve()
{
      ll n;
    cin>>n;
    string a,b;
    cin>>a>>b;
    ll count=0,temp,temp1=1;
    
   ll l=0;
    for(ll i=0;i<n ;i++)
    {
        
        if(a[i]<b[i])
        {
            temp+=count+1;
           count=0;
          
        }
        else
        {
            count++;
        }
        
    }
    
    cout<<temp<<endl;
}

int main() {
	// your code goes here
	ll t;
	cin>>t;
	while(t--)
	{
	    solve();
	}
	return 0;
}

air_sagnik · November 23, 2021, 7:33am

abja
bcab
This test case according to the solution gives an answer 3
But according to the problem statement
we will have to consider
abja and bcab
bja and cab
ja and ab
a and b
if this would have been the case then answer would be 1
but the sol gives the ans as 3
considering
aba and bcb ignoring just the greater part

kishan2402 · November 23, 2021, 8:40am

thank you

resilient_nik9 · November 23, 2021, 8:55am

Can anyone suggest how this solution is giving wrong answers
**#include <bits/stdc++.h>
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t–){
int n;
cin >> n;
string a, b;
cin >> a >> b;
int prev = 0, cnt = 0;
for(int i = 0; i < n; i++){
if(a[i] < b[i]){
cnt += (i - prev + 1);
prev = i;
}
else if(a[i] > b[i]){
prev = i + 1;
}
}
cout << cnt << “\n”;
}
return 0;
}**

athrv · November 23, 2021, 1:51pm

I used suffix sum arr for both the string but got wrong ans for some test cases, I would be great if someone pointed out where I am mistaken…

void solve(string a, string b, int n) {
    vector <int> ar(n), br(n);
    // creating the for storing the suffix sum.
    
    ar[n-1] = a[n-1] - 96; // convert alhpabet to num (a -> 1, b -> 2);
    for(int i = n-2, i >= 0; i++)
        ar[i] = a[i] - 96 + ar[i + 1];
    // if a = aaa the ar = {3, 2, 1}
    
    br[n-1] = b[n-1] - 96;
    for(int i = n-2, i >= 0; i++)
        br[i] = b[i] - 96 + br[i + 1];

    int ans = 0
    for(int i = 0; i < n; i++) 
        if(ar[i] < br[i]) ans++;
    
    cout << ans << endl;
}

suman_18733097 · November 23, 2021, 2:14pm

Before you go through the test case your code fails, we will first rectify your code that has some bugs. Here’s the rectified version:

void solve() {
	string a, b;
	int n;
	cin >> n >> a >> b;
    vector <int> ar(n), br(n);
    // creating the for storing the suffix sum.
    
    ar[n-1] = a[n-1] - 96; // convert alhpabet to num (a -> 1, b -> 2);
    for(int i = n-2; i >= 0; i--)
        ar[i] = a[i] - 96 + ar[i + 1];
    // if a = aaa the ar = {3, 2, 1}
    
    br[n-1] = b[n-1] - 96;
    for(int i = n-2; i >= 0; i--)
        br[i] = b[i] - 96 + br[i + 1];

    int ans = 0;
    for(int i = 0; i < n; i++) 
        if(ar[i] < br[i]) ans++;
    
    cout << ans << '\n';
}

Now, consider the following test case.

Input

4
5
lbmbc
rbqhd
3
rok
zwk
5
hdqcx
idsdr
6
mwrsyl
ofxjbd

Expected Output

Your Output

piyushsri1999 · November 23, 2021, 4:07pm

What is wrong with this code please anyone help thanks.

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while(T–>0){
int n=sc.nextInt();
String a, b;
a=sc.nextLine();
b=sc.nextLine();

      boolean condition=false;
      int count=0;
      for(int i=n-1;i>=0;i--){
          System.out.println(i);
          if(a.charAt(i)==b.charAt(i)){
              if(condition){
                  count++;
              }
          }
          else if(a.charAt(i)<b.charAt(i)){
             
              count++;
               condition=true;
          }
          else{
              condition=false;
          }
      }
      System.out.println(count);
      
      
      
      
    }
}

}

athrv · November 23, 2021, 4:31pm

Ohhh, I get it now…
if given strings are a = az and b = bd… my solution would give
wrong ans as 0, as the ‘z’ in str a is greater but ‘bd’ is lexicographically smaller than ‘bd’…
Thank you so much for your support

hrishi_53 · November 24, 2021, 3:57am

#include
using namespace std;

int main() {
// your code goes here
int T;
cin>>T;
while(T–){
int count=0;
int n;
cin>>n;
char a[n],b[n];
cin>>a>>b;
for (int i=0;i<n;i++){
if(i==n-1 && a[i]<=b[i]){
if(a[i]==b[i]){
break;
}
count++;
break;
}
if(a[i]==b[i]){
if(a[i+1]<=b[i+1]){
count++;
}
}

         else {
             if(a[i]<b[i]){
            count++;}
        }
        
    }
    cout<<count<<"\n";	}
return 0;

}
can any one tell, what was the mistake in this??

dflabs_83 · November 24, 2021, 6:23am

Initialize temp , you can remove the power function, it is worthless.

suman_18733097 · November 24, 2021, 1:54pm

Consider this test case.

Input

1
3
urp
urn

Expected Output

Your Output

suman_18733097 · November 24, 2021, 1:56pm

Did you check if any of them is an empty string (of course, the input format says strings have a length at least 1, but still are you sure you are reading the strings correctly)?

dev_bok · November 25, 2021, 12:12pm

Hi! Can anyone please help where I am wrong.
Thanks in advance.

#include <iostream>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
using namespace std;
int main() {
fastio;
int t;
cin>>t;
while(t--){
    ll n;
    string s1,s2;
    cin>>n;
    cin>>s1>>s2;
    int tco=0,co=0;
    for(ll i=0;i<n;i++){
        if (s1[i] < s2[i])
        {
            co +=tco+1;
            tco=0;
        }
        else if(s1[i] == s2[i]){
            tco++;
        }
    }
cout<<co<<"\n";
}
}