SUBSPLAY - Editorial

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

Author: Bhavya Rustgi
Tester: Ildar Gainullin
Editorialist: Oleksandr Kulkov

DIFFICULTY:
SIMPLE
PREREQUISITES:
None
PROBLEM:
You’re given a string S. Consider an integer K and two non-empty subsequences A and B each with length K, such that A=B and the amount of common indices in A and B is at most K-1. You have to find maximum value K for which it’s possible.
QUICK EXPLANATION:
Basically the problem asks to find maximum K such that there exist different sets of K indices producing same sub-sequence.
EXPLANATION:
If there are two neighboring same letters, then the answer is n-1 as you may choose same sub-sequences except for these letters. If there are no neighboring letters then the answer is not n-1 and thus we may always remove some letter so that answer won’t change. This process may be repeated until we obtain the sub-sequence which has some neighboring equal letters and has the same answer as initial sequence. So the answer to the problem is defined by the maximum length of sub-sequence having neighboring equal letters, which is the length of the string minus the minimum distance between some pair of repeated letters.

void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	map<char, int> last;
	int ans = 0;
	for(int i = 0; i < n; i++) {
		if(last.count(s[i])) {
			ans = max(ans, n - (i - last[s[i]]));
		}
		last[s[i]] = i;
	}
	cout << ans << endl;
}

AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

9 Likes

Finally an Editorial that i could understand easily!

3 Likes

Can you please help me?
When we try next input:
1
11
abababababc
We expect answer to be 8, but this algorithm outputs 9.

The editorial is great but still If someone is unable to understand how to go through the question,he/she may refer to Link for a more detailed explanation.

3 Likes

Expected answer too is 9 . I think that you are forgetting to count the letter which is getting repeated.

Hey selecting indexes {1,4,5,6,7,8,9,10,11} for A and {3,4,5,6,7,8,9,10,11} for B makes A=B=ababababc of length K = 9.Read the editorial to understand where you are going wrong .

1 Like

Oh, thank you. I thought that indices have to be consecutive numbers.

1 Like

Hey, it would be nice if someone was able to explain that by taking string s as “anax”.

3 Likes

Hey can anyone explain by walking through with an example, not able to understand the editorial.

@melfice When will editorials for all the problems be released? I am waiting for some good editorial of the CHFRAN problem!

@gauravj3
Problem: Given string s, you need to find out two equal maximum (in length) sub-sequences where there must have at least one index difference.

To do that, you need to find out the nearest common letters and remove the letters between them and one of the common letter to get maximum equal sub-sequence length. Few examples as follows:

Given \large s = abcdeda and length of s = 7
Max-Sub-sequence: \large{\color{Red}abc}{\color{Blue}d}{\color{red}a} = > \large{\color{Red} abc}{\color{Blue}d}ed{\color{Red}a} and \large{\color{Red} abc}de{\color{blue}d}{\color{Red}a}
Length of max-sub-sequence: 5
Delete the letters between them and one common letter d then new length will be 5 (answer) => \large abc{\color{Red}de}da
Techniques: Just find out the position difference between two common letters and take minimum one of them and then subtract that length from the total string length. Here two common letters are: a-a and d-d and their position diff is:
a=>6-0 = 6 (zero based indexing)
d=> 5- 3 = 2 then take min(6,2) = 2
Now answer will be: s.size() - 2 = 7-2 = 5

Another example:
Given string \large s = abcddcba
Two maximum sub-sequences are: \large {\color{Red}abc}{\color{blue}d}{\color{red}cba} \small ({\color{Red}abc}{\color{blue}d}d{\color{red}cba})
and \large {\color{Red}abc}{\color{blue}d}{\color{red}cba} \small ({\color{Red}abc}d{\color{blue}d}{\color{red}cba})
Minimum common letters diff: 4-3 =1, ans = 8-1 = 7

Solution Code
  int n, ans = 1e9;
  string s;
  cin >> n >> s;
  int a[27];
  memset(a, -1, sizeof a);
  for (register int i = 0, d; i < n; i++) {
    d = s[i] - 'a';
    if (a[d] != -1) ans = min(ans, (i - a[d]));
    a[d] = i;
  }
  cout << (ans == 1e9 ? 0 : n - ans) << "\n";
7 Likes
  1. It was not clearly mentioned in the problem description if the indices are consecutive or not
  2. It was also not mentioned whether the indices are in ascending order - but this is assumed all over.
  3. Question related to these 2 points during the contest was not answered
2 Likes

Yeah. I assumed consecutive indices and tried many times during contest…The question was not clear.

For video editorial : LINK

5 Likes

The word “Subsequence” claims the meaning supporting 1 and 2.

@shaswat_1234
Problem: Given string s, you need to find out two equal maximum (in length) sub-sequences where t here must have at least one index difference.

To do that, you need to find out the nearest common letters and remove the letters between them and one of the common letter to get maximum equal sub-sequence length. Examples as follows:

Given \large s = anax and length n = 4
Max-Sub-sequence: \large{\color{green}ax} = > \large{\color{yellow}an}{\color{Green} ax} and \large{\color{green} a}{\color{yellow}na}{\color{green}x}
Length of max-sub-sequence: 2
Delete all letters between two common letters a and one common letter a then new length will be 2 (answer) => \large{\color{green} a}{\color{red}na}{\color{green}x} (red colored letters ledeted)

Techniques: Just find out the position difference between two common letters and take minimum one of them and then subtract that length from the total string length. Here common letters are: a-a and their position diff is:
a=>2-0 = 2 (zero based indexing)
Now answer will be: s.size() - 2 = 4-2 = 2

Solution Code
  int n, ans = 1e9;
  string s;
  cin >> n >> s;
  int a[27];
  memset(a, -1, sizeof a);
  for (register int i = 0, d; i < n; i++) {
    d = s[i] - 'a';
    if (a[d] != -1) ans = min(ans, (i - a[d]));
    a[d] = i;
  }
  cout << (ans == 1e9 ? 0 : n - ans) << "\n";

If you need more example, here few of them.

2 Likes

What is wrong with my code? can anyone find it?
I did what is already asked.
Thank you in Advance.

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

    signed main(){

        //freopen("input.txt","r", stdin);

        int t;
        cin>>t;
        while(t--){
            int n;
            string seq;
            cin>>n;
            cin>>seq;

            int hash[26];
            int maxDiff = 1e9;
            bool adj = false;
            memset(hash, 0, sizeof(hash));
            
            for(int i = 0;i < n; i++){
                if(hash[seq[i] - 'a'] == 0){
                    hash[seq[i] - 'a'] = i+1;
                }else if(hash[seq[i] -'a'] != 0){
                    int tempHash = (i+1 - hash[seq[i] - 'a']);
                    maxDiff = min(maxDiff, tempHash);
                    hash[seq[i] - 'a'] = tempHash;
                }
                if(i+1 < n && seq[i] == seq[i+1]){
                    adj = true;
                    break;
                }
            }
            if(adj){
                cout<<(n-1)<<"\n";
            }else if(maxDiff == 1e9){
                cout<<"0\n";
            }else{
                cout<<(n - maxDiff)<<'\n';
            }
        }


        return 0;
    }

can you please help me ,my code is giving right answer in custom inputs but is failing in tasks
my code is :-
#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;
int main (){
ll t;
cin>>t;
for(int p=0;p<t;p++){
int n;
cin>>n;
ll a[100000]={0};
ll b[100000]={0};
string str;
cin>>str;
ll dis=10000000;

    for(ll i=0;i<n;i++){
        a[int(str[i])]++;
    if(a[int(str[i])]==1){
        b[int(str[i])]=i;
    }
    if(a[int(str[i])]==2){
        dis=min(dis,i-b[int(str[i])]);
      
    }

}
      
    cout<<n-dis<<endl;

}

return 0;
}

Where am I going wrong?? Kindly explain…
https://www.codechef.com/viewsolution/34509403