Two Characters

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;

}

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.

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

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?

Wow dude I love your repo so much that I decide to create a similar repo for myself! Keep up the good work!

I know this is a silly question, but I'm curious. What's the reason behind declaring 26 outside main as final int instead of just writing 26 everytime?

Good solution :)

But could it be optimized further ? For Ex. - ab or ba does not matter (means DP table loops could be reduced).

I like your solution better, I used your 'join' approach to get the new string but used regex to see if it passed the criteria. I would post it, but haven't figured out how to paste the code here yet. :)

I used a condition to check if the absolute difference between the counts of the chosen characters is at most 1, which is the case with valid t's. That would make the code quite faster if we had very large strings.

from collections import Counter
from itertools import combinations

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

C = Counter(s)
max_len = 0
for (c1, c2) in combinations(set(s), 2):
    if abs(C[c1] - C[c2]) <= 1:
        t = [c for c in s if c in {c1, c2}]
        if all(t[j] != t[j-1] for j in range(1, len(t))):
            max_len = max(max_len, len(t))

print max_len