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.
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.
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 .
@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";
@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";
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;