- Practice
- Algorithms
- Strings
- Two Characters
- Discussions

# Two Characters

# Two Characters

+ 40 comments **This is definitely not an easy question**. One needs to know regexes and sets to solve this (at least, to solve it in a*reasonable way*). Please reconsider the points and the difficulty of this problem.

+ 23 comments [Spoiler alert]

Here is an overview of my O(n) solution: I created a 26x26 matrix that kept track of each possible 2-letter alternation. If at some point I got an invalid alternation for a pair (which happens when a letter follows itself in that alternation), that combination was discarded.

It's easier to explain with an example. Let's simplify the matrix to just 3 letters:

Input: acbab Matrix begins empty: a b c a b c We begin with the first 'a'. We update the 'a' row and column with that letter as last: a b c a a a a b a c a a b c a a a c b a c c c c c a b c a a b c b b b b c c b c a b c a a a a b a b b c a b c Finally, here comes the last letter: 'b'. Note that there is already a 'b' in combination c-b, so that alternation won't work: a b c a a b a b b b b c a b c

To get the longest alternation, I simply kept track of the amount of updates for each combination in another matrix. When a combination was detected as invalid, I marked its count with -1 and never updated it again.

I hope it's useful for you.

+ 6 comments well a long explanation but i can assure you guys this is complete explanation for this ques plus i have mentioned the methods you can use in between.

Explanation of solution for this problem: step 1. We can recognise all the unique characters in the string using a nested loop and stringname.charAt(index) function. Ex : if string is abcabfacb then unique characters would be : a,b,c,f

i advice you to take a pen and paper for the following steps.

step 2. construct a 2D matrix for the unique characters as following:

`a b c f a b c f`

step 3. run through each letter of the string and update its row and column with the same letter. string = abcabfacb

`for letter a: a b c f a a a a a b a c a f a for letter b: a b c f a a b a a b b b b b c a b f a b`

while going through this process check if you are rewriting an alphabet in some other intersection oher than its diagonal intersection for ex : while updating a(string index =7) on the matrix , status before updating was:

`a b c f a a b a f b b b b f c a b c f f f f f f`

you will notice that there is already a written on a-c intersection. "this means there has been no updation with c alphabet in matrix since previous a alphabet" this suggests that formation of t string is not possible with a-c combination. further going through this step you will find out that with a-c, a-f and b-f have also been ruled out. thus combinations: a-b,b-c and c-f are suitable to form the t string.

step4 : now to find the longest t string i suggest you to construct another similar matrix with those unique characters and update the intersection by adding 1 to that intersection which is being checked in the iteration and update -1 in matrix where the combination is not valid. i will write the final matrix for you guys: ruling out the same letter combinations(representing them by x)

`a b c f a x 6 -1 -1 b 6 x 5 -1 c -1 5 x 3 f -1 -1 3 x`

i want you guys to carefully observe the above matrix you will notice that the a-b combination row/column has been updated the most. hence obviously the longest t string will contain these two letters.

step 5: you can print directly the no. of updations on the screen or find out the t string by eliminating the other characters by using the method: s=s.replace("c",""); s=s.replace("f","");

i think you can understand what the method does by its name itself.

phew that was a very long explanation. surely this ques was not an easy one. i wrote this long explanation because this way of solving the ques was very interesting but a bit tricky and can be applied to various other questions. thank you guys for reading it thoroughly.

+ 7 comments #include <bits/stdc++.h> using namespace std; string a = "abcdefghijklmnopqrstuvwxyz"; //dr0opy int main() { int n; cin>>n; string s; cin>>s; int maxi=0;//to cal the max length of the possible string for(int i=0;i<26;i++){ for(int j=i+1;j<26;j++){ char x=a[i]; char y=a[j]; string t=""; for(int k=0;k<n;k++){ if(s[k]==x||s[k]==y){ t+=s[k]; } } //cout<<t<<endl; bool flag=true; for(int f=0;f+1<t.size();f++) { if(t[f]==t[f+1]) { flag=false;break; } } int ts=t.size(); if((flag)&&(ts>1)) maxi = max(maxi,ts); } } cout<<maxi<<endl; return 0; }

it took me

**4 months**and finally did it ;)

+ 1 comment Why is this classified as 'easy'. Great question, but this is very misleading for newbies.

Sort 885 Discussions, By:

Please Login in order to post a comment