# STRCOMPARE - Editorial

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

Simple

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 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){
}
long long readIntLn(long long l,long long 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()
{

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;

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 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){
}
long long readIntLn(long long l,long long 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()
{

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;

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;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

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

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

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

6 Likes

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);
}
}

#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.

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

1 Like

You can verify it here â Standard Template Library | HackerEarth

1 Like

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.

1 Like

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

1 Like

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

``````#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() {
ll t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}

``````

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

1 Like

thank you

1 Like

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;
}**

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;
}
``````

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

``````5
2
4
2
``````

``````5
2
0
0
``````

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);

}
}
``````

}

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

1 Like

#include
using namespace std;

int main() {
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??

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

1 Like

Consider this test case.

Input

``````1
3
urp
urn
``````

Expected Output

``````0
``````

``````1
``````

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)?

``````#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";
}
}

``````