The solution to this certainly doesn't need regex. And I'm pretty sure that basic usage of sets (just finding unique entries in a string) counts as an easy problem.

The question is phrased to intentionally lead you to a difficult solution, so figuring out what the easy solution is may make it not an 'easy question'.

Edit: Lots of downvotes on this comment I see... Since I just pointed out that only basic usage of a set is needed to solve this reasonably (and certainly not any regex), and I agreed that it may not be an 'easy' question, I'm a bit confused...

def validate(cpy):
    for i in range(len(cpy)-1):
        if cpy[i] == cpy[i+1]:
            return False
    return True

for _ in range(int(input().strip())):
    s = input().strip()
    st = list(set(s))
    max_len = 0
    for x in range(len(st)):
        for y in range(x+1, len(st)):
            cpy = [c for c in s if c==st[x] or c==st[y]]
            if validate(cpy):
                max_len = max(max_len, len(cpy))
    print(max_len)

The problems submitted by user nabila_ahmed are always misleading and does not contain the standard weight/points. E.G a difficult problem is worth 15 points whereas a simple problem is worth 30 points. Plus this user also does not provide enough sample test cases.

You can bruteforce it in O(|s|), what do you mean by 'reasonable'?

I don't know if that's the only way to solve this problem, but I remember thinking that it was poorly worded, e.g. there's no explanation of what input strings would cause a "0" output. Interesting nonetheless.

I also though the same before solving it..but its actually not that tough..easy is appropriate tag.

YES

Or maybe a hint like 'brute force' (taking a cue from the editorial solution).

I don't know anything about Regex, so I do a little research and finally solve the problem.

The author suggests brute forcing it and that's a reasonable approach for a live contest (since limits are fairly small). For a practice section - would be nice to have a hint, success rate would be higher :)

And just for fun - about a proper approach to solve this - I vote for using indexing and sorted arrays comparasion. That could be an easy task in the Arrays section.

You can actually brute force it in linear time because you just choose 2 letters from the alphabet and try to use those at the 2 in t. You can then check if this is an alternating sequence in linear time. Neither regex not sets are needed. You could make this faster using sets by only checking combinations of the letters in the original string, but this is not necessary when you can do it in at most 325000 operations.

One more solution without regexp:

import itertools

def is_t(s):
    if len(s) < 2:
        return False
    return all(c == s[0] for c in s[2::2]) and all(c == s[1] for c in s[3::2])

s_len = int(input().strip())
s = input().strip()

chars_in_s = { list(s) }

max_t_len = 0

for c1, c2 in itertools.combinations(chars_in_s, 2):
    filtered_str = ''.join(c for c in s if c in {c1, c2})
    if is_t(filtered_str):
        max_t_len = max(max_t_len, len(filtered_str))
        
print(max_t_len)

May be not the fastest, but passes tests and easy to understand.

Hey! in fact I was wondering what is a better way of doing this, in my solution I went for all letters in the alphabet and try every combination of the letters i.e. 26*(27)/2 = 351 iterations.

But if you change a little the problem say for example, instead of only alphabet character you use all the posible characters i.e. 300(301)/2 = 45 150 iterations or worst you could use any number instead of character this becomes (n comb 2) = O(n!) horrible!!!!.

So there must be a better way, and that's what I'm looking for, any posibility?.

My C# solution without known of regexes:

static void Main(String[] args) {
        int len = Convert.ToInt32(Console.ReadLine());
        string s = Console.ReadLine();
        //my code
        int temp = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (s[i] != s[j]) {
                    bool gfn = true;
                    Stack<char> sta = new Stack<char>();
                    foreach (char c in s) {
                        if (c == s[i] || c == s[j]) {
                            sta.Push(c);
                        }
                    }
                    char[] ca = sta.ToArray();
                    for (int k = 0; k < ca.Length - 1; k++) {
                        if (ca[k] != ca[k+1] && gfn == true) {
                            gfn = true;
                        }
                        else {
                            gfn = false;
                        }
                    }
                    if (gfn == true && ca.Length > temp) {
                        temp = ca.Length;
                    }
                }
            }
        }
        Console.WriteLine(temp);
    }

Also the T(n) = O(n^3), it did work:)

but even brutal force can solve it

Since we have only 26 characters, we can easily brute force and try all combinations of 2 characters. Not the most efficient solution, but valid for all cases:

In c++, call this function for each combination of two characters:

int count_alternating(const string &s, char c, char d) {
    int n = 0;
    bool last_c = false;
    bool last_d = false;
    for (char a : s) {
        if (a == c) {
            if (last_c) return 0;
            n++;
            last_c = true;
            last_d = false;
        }
        if (a == d) {
            if (last_d) return 0;
            n++;
            last_c = false;
            last_d = true;
        }
    }
    return n;
}

Loop over each 2-char combination and keeping the maximum length value:

cin >> s;
    int m = 0;
    if (s.size() > 1)
        for (char c = 'a'; c <= 'z'; c++) {
            for (char d = 'a'; d <= 'z'; d++) {
                if (c == d) continue;
                int n = count_alternating(s, c, d);
                if (n > m) m = n;
            }
        }

Thank you this comment, I was like it is tagged as simple problem and for the last 15 min I am not able to get the answer, in my mind i thought what kind of developer I am who can't solve a simple problem. Yes it's a tough one

Required a bit a thinking, perhaps should have been a medium question.

Here is my Python3 solution (i'm sure it may be tougher in other languages)

from itertools import combinations
_, s = input(), input()
max = 0
s_set = set(s)
length = len(s_set)
if length > 1:
    for c in combinations(s_set,length-2):
        new_s = s
        for ch in c:
            new_s = new_s.replace(ch,'')
        if len([i for i in range(len(new_s)-1) if new_s[i] == new_s[i+1]]) == 0:
            if len(new_s) > max: max = len(new_s)
print(max)

doesnt need regex, simple o(n) solution exists.

First I totally misunderstood the problem, but now I got it. Here's my Python2 solution without regex (with the help of itertools):

def twoCharaters(s):
    combinations_of_two_letters = [i for i in combinations(set(s), 2)]
    stack = []
    
    for tupl in combinations_of_two_letters:
        copy_s = copy.deepcopy(s)
        for letter in copy_s:
            if letter not in tupl:
                copy_s = copy_s.replace(letter, '')
        stack.append(copy_s)

    copy_stack = copy.deepcopy(list(set(stack)))
    for item in copy_stack:
        for index, j in enumerate(item):
            if item[index:(index+2)] == j*2:
                stack.remove(item)
                break
    return len(max(stack, key=len)) if stack else 0

was hoping for this comment after reading the question.

It's not easy if you don't possess some knowledge beyond the absolute basics of python. In my solution I used sets and list comprehensions for example.

On the other hand the problem is not hard in temrs of optimization. The brute force approach works just fine and passes every test case.

I think it is easy, but the solution is definitely longer. Because the solution is longer than alot of the easier problems here( the ones with a high success rate) a case could be made for it being medium. However, it's nice to have easy problem that are not completely trivial; the ones that are only a few lines long. To be honest, this one took me about 100 lines. I already knew my version was overkill, but I decided to do it that way anyway. I tend to do that alot with easy problems. Just go straight into optimization.

Agree! I did in PHP but wasn't easy.

here is mine

int main() { int len; cin>>len;

string str;
cin>>str;

int max_len=-1;
int no_come=0;


string a = "abcdefghijklmnopqrstuvwxyz";
int enter_1=0;

for(int i=0; i<25; i++) { for(int k=i+1; k<26; k++) { char s_1=a[i]; char s_2=a[k];

        char str_update[1001]={'0'};

       int x1=0;
   for(int t=0; t<len; t++)
   {   if(s_1==str[t])
      { 
       str_update[x1]=str[t]; 
       x1++;
      }

       if(s_2==str[t])
      {  
         str_update[x1]=str[t];
         x1++;
      }

   }  




      string str1(str_update);


       int len1= str1.length();


       int wr=0;

       for(int l=0; l<len1-1; l++)
       {   enter_1=1;


           if(str1[l]!=str1[l+1])
           {

           }
           else
           {   
               wr=1;
               break;

           }

       }

       if(wr==0 &&len1>=2)
       {
           if(len1>max_len)
               max_len=len1;
           no_come=1;

       }




   }

}

if(no_come==1)
 cout<<max_len<<endl;
else
    cout<<"0"<<endl;

}

i tottaly agree with u bro!!!

Yes.

6 hours spent on this to solve this EASY one :-)

This is not easy problem.
We dont even think the way question asks.
(Even editorial has only 1 solution, and its in python, in general c++ or java is given)

More details below, if you are interested.

I dint do any of this kind before, so
.. approch1 dint even pass sample tests. delete continuous chars, delete single char, all that is wrong. ~5 hours wasted
.. approch2 passed all. 30 mins spent
.. approch0, the one given in Editorial, brute force with delete, mine doesn't do neither in approch2.

I have sent email to support@hackerrank.com to change this difficulty to Medium, with link to the parent witht 400+ upvotes as of today.

using regex. the easiest way i could think of.

static int alternate(string s) {
  int max = 0;
  var hset = new string(s.Distinct().ToArray());
  string tmp;
  for (int i = 0; i < hset.Length; i++)
  {
    for (int j = i + 1; j < hset.Length; j++)
    {
      tmp = Regex.Replace(s, @"[^" + hset[i] + hset[j] + "]", "");
      if (tmp.Length > max && !Regex.IsMatch(tmp, @"([a-z])\1+"))
        max = tmp.Length;
    }
  }
  return max;
}

How did you think of this? Is this technique called something? It's super interesting, and I'd love to see it applied in other circumstances too!

i didn't understand anything about your solution.

I was considering the same thing but thought I was crazy. Here's a Java example for anyone who is curious for the actual algorithm. I believe it's technically O(n) time and O(1) space. Although there are many loops and 2D arrays, they involve the 26 alphabet-size constant.

public static int longestAltString(String s) {
    char [][] letters = new char[26][26];
    int [][] values = new int[26][26];
    for(char c : s.toCharArray()) {
        int index = (int)(c - 'a');
        for(int i = 0; i < 26; i++) {
            if(letters[index][i] != c && values[index][i] != -1) {
                letters[index][i] = c;
                ++values[index][i];
            } else {
                values[index][i] = -1;
            }
            if(letters[i][index] != c && values[i][index] != -1) {
                letters[i][index] = c;
                ++values[i][index];
            } else {
                values[i][index] = -1;
            }
        }
    }
    int largestString = 0;
    for(int i = 0; i < 26; i++) {
        for(int j = 0; j < 26; j++) {
            if(values[i][j] > largestString) {
                largestString = values[i][j];
            }
        }
    }
    if(largestString > 1) {
        return largestString;
    } else {
        return 0;
    }
}

Hi Racsoth,

I got similar but faster algorithm for this. I first count the apperance of each char in the given string 's'. Then, I sort these char in decending order. Finally, create a double loop as the matrix representation and only loop through the upper triangle elements to construct the new string 't'.

Therefore, the first effective nonzero length of the 't' is the answer.

Here is my code:

using namespace std;

bool myCompare( pair lhs, pair rhs){ return lhs.first > rhs.first; }

vector > getOrderedChar(const string & s){ map count; for(unsigned i=0 ; i

vector<pair<int,char> > orderChar;
for(auto it: count){
    orderChar.push_back({it.second, it.first});
}

sort( orderChar.begin(), orderChar.end(), myCompare );
return orderChar;

}

int getCount(string & str, char a, char b){ // Construct t from a, b only. string tmp; for( unsigned i ; i

int main(){ int len; cin >> len; string s; cin >> s; auto orderCharVec = getOrderedChar(s);

int maxCount = 0;
bool needIteration = true;
for( int i=0 ; i<orderCharVec.size()-1 and needIteration ; i++){
    for( int j=i+1 ; j<orderCharVec.size() and needIteration ; j++){
        char a = orderCharVec[i].second;
        char b = orderCharVec[j].second;
        int count = getCount(s, a, b);
        if( count > 0 ){
            maxCount = count;
            needIteration = false;
        }
    }
}
cout<<maxCount<<endl;

return 0;

}

hi there

can you explain what type of a problem is this? is it some kind of dynamic programming

Very clever DP solution. The sub problems are the substrings of an input.

This is one of the most beautiful piece of artforms.

awesome job buddy!!!

Thanks for the explanation. I was able to solve the problem after looking at your logic.

Interesting approach. Quite simple and effective - keep track of every pair in 2d-array. O(n). Passed.

Great idea! Thank you.

yep, that's the right way to do this...

Here is the python solution for this algorithm:

https://github.com/skynyrd/algo/blob/master/hacker_rank/algorithms/string/two_characters.py

Can you pleae explain the usage of last step you have used.I'm not able to get the usage of the last step..i.e..eliminatig the c-b combination.

Genius solution. Thanks for sharing!

The solution is: for each character combination of 2, consider if it's possible for them to be the only remaining characters.

ex: aacbb
There are 3 scenarios to consider:
1. only 'a' and 'b' remaining. It's "aabb", and doesn't satisfy the criteria.
2. only 'a' and 'c' remaining. It's "aac", also not okay.
3. only 'b' and 'c' remaining. It's "cbb", also not okay.

So, in the following 3x3 matrix:
  a b c
a 
b 
c 
(a,b) or (b,a) represents the scenario "only 'a' and 'b' remaining". 
When we read the first 'a' in "aacbb", the matrix becomes:
  a b c
a a a a
b a
c a

so for (a,b), or "if you want only 'a' and 'b' in the remaining string", the 'a' will be the last character. Then we add the second 'a' in "aacbb". Notice that for (a,b), 'a' is already the last character and adding it will create an "aa" duplicate. Thus (a,b) is impossible.

Hope this explanation makes it clear. If not, writing down on a paper helps. My code:

int alternate(string s) {
    array<array<char,26>,26> tbl_dup;
    array<array<int,26>,26> tbl_cnt;

    // Initilization
    for (int i(0); i < 26; ++i) {
        for (int j(0); j < 26; ++j) {
            tbl_dup[i][j] = '\0';
            tbl_cnt[i][j] = 0;
        }
    }

    // Go over s
    for(int i(0);i<s.size();++i){
        char ch = s[i];
        for(int j(0);j<26;++j){
            if (tbl_dup[ch-'a'][j] == ch){
                // The combination of the char ch and the char 'a'+j is impossible.
                tbl_cnt[ch-'a'][j] = -1;
                tbl_cnt[j][ch-'a'] = -1;
            }
            else{
                bool no_longer_count = (tbl_cnt[ch-'a'][j] == -1);
                tbl_dup[ch-'a'][j] = ch;
                if(!no_longer_count)
                    ++tbl_cnt[ch-'a'][j];

                if((ch-'a')!=j){
                    tbl_dup[j][ch-'a'] = ch;
                    if(!no_longer_count)
                        ++tbl_cnt[j][ch-'a'];
                }
            }
        }
    }

    int max = -1;
    for(int i(0);i<26;++i){
        for(int j(i);j<26;++j){
            if(tbl_cnt[i][j] > max)max = tbl_cnt[i][j];
        }
    }
    return (max<=1)?0:max;
}

really, it was a very interesting solution, thanks a lot

The slightly optimized (no sort required at all) C++ version with const memory requirement and O(1) algorithm complexity is this:

int maxLen(string s)
{
  // Step 0: do not process 0 strings
  if (s.empty())
    return s.size();

  // Step 1: find unique letters
  string unique;
  for (auto c = s.cbegin(); c < s.cend(); ++c)
    if (unique.find(*c) == string::npos)
      unique.push_back(*c);

  // Step 2: create small cross index table
  unsigned crossIndex[26];
  for (auto i = 0; i < 26; ++i)
    crossIndex[i];
  for (auto i = 0; i < unique.size(); ++i)
    crossIndex[('z' - unique[i])] = i;

  // Step 3: create and initialize letter and count tables
  const string::size_type ts = unique.size();
  char  letter[ts][ts];
  int   count[ts][ts];
  for (auto i = 0; i < ts; ++i)
    for (auto j = 0; j < ts; ++j)
      count[i][j] = 0;
      
  // Step 4: cycle around the string and fill the tables
  for (auto c = s.cbegin(); c < s.cend(); ++c)
  {
    const unsigned index = crossIndex['z' - *c];

    for (auto i = 0; i < ts; ++i)
    {
      if (count[index][i] != -1 && letter[index][i] != *c)
      {
        letter[index][i] = *c;
        ++count[index][i];
      }
      else
        count[index][i] = -1;

      if (count[i][index] != -1 && letter[i][index] != *c)
      {
        letter[i][index] = *c;
        ++count[i][index];
      }
      else
        count[i][index] = -1;
    }
  }

  // Step 5: iterate over the count table
  int result = 0;
  for (auto i = 0; i < ts; ++i)
    for (auto j = 0; j < ts; ++j)
      result = max(result, count[i][j]);

  return (result > 1 ? result : 0);
}

Thanks a lot for this.

It is not easy ?

My thought is also the same. This is defintely not easy.

great code dr0opy helped a lot . but the string a = "abcdefghijklmnopqrstuvwxyz"; part if placed inside the main body all the test cases arent being right

here is an OPTIMIZED VERSION of your solution.

using namespace std;

int main ()

{

int len;
cin >> len;

string s;
cin >> s;

vector <int > a(26,0);
string t = "";
int i = 0, j;

while(s[i] != '\0')
    {
    int in  = s[i] - 97;
    a[in]++;
    i++;
}

for(int i = 0; i < 26; i++)
    {
    if(a[i] != 0)
        {
        t = t + char(97+i);
    }
 //   cout << a[i]<<" ";
}

int m = 0;

for(int i = 0; i  <t.length(); i++)
    {
    for(int j = i+1; j < t.length(); j++)
        {
        char x = t[i];
        char y = t[j];
        string h = "";

        for(int l = 0 ; l < len; l++)
            {
            if(s[l] == x || s[l] == y )
                {
                 h = h+ s[l];                    
            }
        }

        int f = 1;

        for(int q = 0; q < h.size()-1; q++)
            {
            if(h[q] == h[q+1])
                {
                f =0;
                break;
            }
        }

        if(f && h.size() > 1)
            {
            int size = h.size();
            m = max(size,m);
        }
    }
}

cout << m;

return 0;

}

what a problem to check only those charcter which are present in inputed string?

But your soolution was very easy to understand...

I was literally frustuated while solving this problem and only half of the testcases passed through my soln...

Thanks dude..