- Practice
- Algorithms
- Strings
- Two Characters
- Discussions

# Two Characters

# Two Characters

smddzcy + 34 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.PatrickSJackson + 16 comments 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)

smddzcy + 5 comments This shouldn't be counted as easy

*if*you consider other easy questions. Also about the regex; I didn't say "*needed*", I said "*to solve it in a reasonable way*". I certainly don't like to use 5 iterations instead of 4 for an*easy*question. (I know there are easier and faster ways than my solution but I don't like to think a lot too, for an*easy*question) This is a mediumish question and the points should be at least 20 or 25, not**15**.thejase + 1 comment I hear ya, but no one really uses this kind of pattern with strings, but sets of objects and graphs. Running algorithms on strings is just easier to comprehend for some, and that's why we use them as practice. That said, regex as a

*reasonable way*limits the usage breadth of the concept and simply states the problem-solver's limits.It's not that difficult really. Maybe the points could be a little higher, but I wouldn't say this isn't easy.

g_sp1 + 2 comments if this is counted as "easy" then i guess the user will ask to write algo to deploy civilization on Mars as Difficult/Hard question

thejase + 1 comment Haha, I wouldn't trust anyone on my Mars team who thinks this is too difficult (after some time spent thinking and researching). Easy doesn't mean you can just pound out a one-liner or know every aspect/case right away.

Quazar777 + 1 comment then what're you doing in the discussions? People normally open this tab only when they either can't solve a problem or have solved it with great difficulty and want to see what others are saying about it.

williamng + 0 comments Well, there are edge cases, right? I guess that guy is the edge case, lol. Me too, :). Well, I just like to bask in the difficulties of others.

tanish20bali + 0 comments hahahahahahaha

Silver_Shark + 2 comments sir ....can you give me little detail about regex and from where can i learn about it

rock_solid + 1 comment regex take this

booleanand + 0 comments [deleted]

adityasuman2025 + 1 comment regex101.com

kevinhs472 + 0 comments thank you sir

holamson + 0 comments all that's needed is to remember the frequency of the characters, and determine if a pair of characters is alternating or not. As you iterate through the string, the current character is c1. Two characters c1, c2 are

**not**alternating if last[c1]>last[c2] where 'last' remembers the last position that a character appears.Nuthin + 0 comments While you're arguing whether it is easy you're missing the fact that it's not correct

kapploneon + 0 comments I defintely agree with this. Without regex knowledge it seems you are just reinventing the wheel.

tsbankole + 2 comments i added a bit to the code with an if condition

#!/bin/python3 import sys def validate(inp): for i in range(len(inp)-1): if inp[i+1]==inp[i]: return False return True s_len = int(input().strip()) s = input().strip() ans = 0 chtoindex = [] for ch in set(s): chtoindex.append((ch, len([j for j, x in enumerate(s) if x == ch]))) for i, pack in enumerate(chtoindex[:-1]): char_i, lenchar_i = pack[0], pack[1] for j, otherpack in enumerate(chtoindex[i+1:]): char_j, lenchar_j = otherpack[0], otherpack[1] if abs(lenchar_i-lenchar_j)<2: c = [cha for cha in s if cha is char_i or cha is char_j] if validate(c): ans = max(ans, lenchar_j+lenchar_i) print(ans)

lnsnarayanan + 1 comment I kinda came up with a long logic with python making use of itertools

def alternate(s): results=[] st=list(set(s)) if len(st)<2: return 0 else: combos=list(combinations(st,len(st)-2)) print(combos) for i in combos: vals=[] temp=s for x in i: temp=temp.replace(x,"") print(temp) for y in range(len(temp)-1): if temp[y]==temp[y+1]: vals.append(False) else: vals.append(True) if all(vals)==True: results.append(len(temp)) else: results.append(0) return max(results)

gawalivj + 0 comments nice ...........

wanghaitang_ufl + 0 comments Looks I will need to work on python. My c++ code is a lot more complicated, despite that I have used a similar approach.

However, if anyone can modify my map loop, please let me know. https://www.hackerrank.com/challenges/two-characters/submissions/code/48031321

ranjan_purbey + 0 comments The first line in input is length of string s and not the number of test cases. Hence the outer for loop shouldn't be there.

supragya_23 + 0 comments how did u remove runtime error in ur code?

jaco0797 + 0 comments man this is such great code. thanks for sharing

Lisanaaa + 0 comments your code

for _ in range(int(input().strip())):

is unnecessary.

timbo1 + 0 comments This was essentially my solution. My problem with this challenge, though, is that it's significantly more difficult than the problems that proceed it yet it is marked as easy.

vishal_pandey1 + 0 comments I really like your solution, I couldnt find one every after an hour but seeing after your solution it feels that I need to think more

2017ugcs037 + 0 comments pretty nice man!!!!!!

SHWAUBH + 0 comments This seems to be a BruteForce method..can you optimize your solution to preety much greedy..

SundayBro + 0 comments Your solution is on point. It only times out because you check every single character in the string. That's the reason to the downvotes. To put it simply, you have to create a list containing the unique characters in your string in order to spare some time.

GAURAV7656 + 0 comments [c for c in s if c==st[x] or c==st[y]]

would you make me understand the a bove line

ananraddad + 1 comment 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; }

dhivya14mail + 0 comments can u explain me this code?

arushiibajpai + 0 comments That is an O(n^3) complexity. we can't go with a cubic complexity solution

adityadhanraj789 + 0 comments [deleted]

mchisty + 1 comment 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.

JC_The_Techie + 2 comments She's so cute though.....

Bishwajit_007 + 0 comments LOL

Devu21 + 0 comments [deleted]

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

h0193250 + 1 comment what do you mean by O(|s|) ? How would you do that?

beastieric + 2 comments O(|s|) means that the solution is in linear time, with the factor being the length of string s. In order to do this, you can try all possible combinations of two letters and see which one produces the longest string t, which can be done in O(|s|).

kaiwangcanada + 1 comment The number of all possible combinations of 2 letters is n*(n-1)/2, which is n^2. I think it means the complexity is O(n^2).

durumu + 1 comment Not quite. All possible combinations of 2 letters is k*(k-1)/2, for an alphabet of size k. Since the alphabet in this case is a fixed size, i.e. k = 26, all possible combinations of 2 letters can be checked in 325 iterations for any input of size n, which is O(1). I agree that if the alphabet was variable size, this would be O(n^2).

welcometors + 0 comments You are correct and the total complexity will be O(|s|.n^2). How ever this can be easily done in O(|s|.n + n^2) with the help of O(n^2) space. Which is a good trade off for a smaller n.

chirag_mo + 1 comment Hi Beastieric, i think its not possible for creating a set using O(|s|), you need minimum of 2 nested loops. And generally since we take the highest order of running time in any program,this program runtime is > O(|s|)

beastieric + 2 comments Yes, there is two nested loops. However, because there is a fixed number of letters in the alphabet, the two nested loops runs in constant time. The actual running time of this algorithm would be 26*26*O(|s|) plus some other constants. Because we ignore constant factors, the running time is O(|s|).

alaniane + 2 comments It is still O(N^2). It is just that N=26. However, it would still be a quadratic running time.

r_i_v_a + 0 comments The English alphabet always has 26 letters regardless of the problem input, so 26 (and 26^2) are only constant factors when talking about runtime. See https://learnxinyminutes.com/docs/asymptotic-notation/

DMJSPECTER07 + 0 comments hey it will be O(CONST*|S|)!!!!

desaim + 1 comment 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.

r_i_v_a + 0 comments Strings that should cause a 0 output:

aaaabbbbcccc

aaaabababbbb

cccccccccccc

If the string does not have some pair of letters that alternate with each other when you ignore all other letters in the string, it should output 0.

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

shrkntagarwal + 3 comments can u solve it in java?

BALYAM_muralidh2 + 5 comments import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static int twoCharaters(String s,String noDup) { if(s.length()==2){ if(s.charAt(0)!=s.charAt(1)){ return 2; } } int temp = 0; for(int i =0 ;i<noDup.length();i++){ char a = noDup.charAt(i); for(int j =i+1;j<noDup.length();j++){ char b = noDup.charAt(j); String t = Form(a,b,s); if(checkT(t)==true){ if(t.length()>temp){ temp = t.length(); } } } } return temp; } public static String Form(char a,char b,String s){ String newString = ""; for(int i=0;i<s.length();i++){ if(s.charAt(i) == a){ newString+=a; } if(s.charAt(i)==b){ newString+=b; } } return newString; } public static boolean checkT(String s){ boolean a = false; int count = 0; for(int i=0;i<s.length()-2;i++){ if(s.charAt(i)==s.charAt(i+2)){ count++; a = true; }else{ a = false; } } if((count == s.length()-2) && (a==true) ){ return true; } return false; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int l = in.nextInt(); String s = in.next(); String noDup = removeDuplicates(s); int result = twoCharaters(s,noDup); System.out.println(result); in.close(); } public static String removeDuplicates(String string){ char[] chars = string.toCharArray(); Set<Character> charSet = new LinkedHashSet<Character>(); for (char c : chars) { charSet.add(c); } StringBuilder sb = new StringBuilder(); for(Character character : charSet) { sb.append(character); } String newString = sb.toString(); return newString; } }

java code

js_doozy + 2 comments static int twoCharacters(String s){ Set<Character> char_set = new HashSet<Character>(); for (int i = 0; i < s.length(); i++) { char_set.add(s.charAt(i)); } Character[] char_arr = char_set.toArray(new Character[char_set.size()]); int max = 0; for (int j = 0; j < char_arr.length - 1; j++) { for (int k = j + 1; k < char_arr.length; k++) { String pattern = "([^" + char_arr[j] + char_arr[k] + "])"; String trimmedStr = s.replaceAll(pattern, ""); if (isTwoCharacter(trimmedStr) && trimmedStr.length() > max) { max = trimmedStr.length(); } } } return max; } static boolean isTwoCharacter(String s) { for (int i = 0; i < s.length() - 1; i++) { if (s.charAt(i) == s.charAt(i+1)) { return false; } } return true; }

liuyuhao717 + 0 comments Hi, Can you explain why this is working? I know your algorthmn but I don't know how it is going to handling when there is a case require to delete three character instances.

Maybe I didn't know regex very well I am sorry for that.

Benjii + 0 comments Can you please explain your code

deoramanas + 1 comment working?

BALYAM_muralidh2 + 1 comment you mean my code?yes its working

deoramanas + 1 comment all testcases?

BALYAM_muralidh2 + 0 comments yes

gokulYadav + 0 comments Very understandable code Thanks...

asif0228 + 0 comments [deleted]azaystudy + 1 comment Good solution, all tests passed using this approach. For those who didn't understand the logic -

- First of all identify all the distinct characters in string. To do this, we have removed duplicates from original string using a set.
- Now iterate over distinct characters in pairs, use the string having no duplicates which we generated in above step.
- Form the potential final string having this pair of characters. To do this, iterate over original string and check for occurrences of these two characters and add them to potential string.
- Now check the validity of potential string for alternate characters
- If potential string is valud, keep count of max length of such strings to get the final answer.

pawankashyap022 + 1 comment can you send the code also

azaystudy + 0 comments `static int alternate(String s) { if(s.length() == 2 && s.charAt(0) != s.charAt(1)) { return 2; } String noDups = removeDuplicates(s); int max = 0; for(int i=0; i<noDups.length(); i++) { char a = noDups.charAt(i); for(int j=i+1; j<noDups.length(); j++) { char b = noDups.charAt(j); String t = formString(s, a, b); if(isValid(t)) { if(t.length() > max) { max = t.length(); } } } } return max; } //form string from original string using these two chars static String formString(String s, char a, char b) { String newString = ""; for(int i=0; i<s.length(); i++) { if(s.charAt(i) == a) { newString += a; } if(s.charAt(i) == b) { newString += b; } } return newString; } static boolean isValid(String s) { for(int i=1; i<s.length()-1; i++) { if(s.charAt(i-1) != s.charAt(i) && s.charAt(i-1) == s.charAt(i+1)) { continue; } else { return false; } } return true; } static String removeDuplicates(String s) { char[] chars = s.toCharArray(); Set<Character> set = new LinkedHashSet<>(); for(char c : chars) { set.add(c); } StringBuilder sb = new StringBuilder(); for(Character c : set) { sb.append(c); } return sb.toString(); }`

asif0228 + 0 comments wrote a clumsy one.

// Complete the twoCharaters function below. static int twoCharaters(String s) { for(int i=1;i<s.length();i++){ if(s.charAt(i-1)==s.charAt(i)) {s = s.replace(s.charAt(i)+"","");i=0;} } String[][] map = new String[26][26]; int r = 0; for(int i=0;i<s.length();i++){ r = ((int)s.charAt(i)) - 97; for(int j=0;j<26;j++){ //System.out.println("[j][r] "+j+","+r); if(map[j][r]==null) map[j][r]=s.charAt(i)+""; else if(map[j][r].equals("N")){} else if(map[j][r].charAt(map[j][r].length()-1)!=s.charAt(i)) map[j][r] += s.charAt(i); else map[j][r]="N"; if(map[r][j]==null) map[r][j]=s.charAt(i)+""; else if(map[r][j].equals("N")){} else if(map[r][j].charAt(map[r][j].length()-1)!=s.charAt(i)) map[r][j] += s.charAt(i); else map[r][j]="N"; } } r = 0; for(int i=0;i<26;i++){ for(int j=0;j<26;j++){ if(map[i][j]!=null && map[i][j].length()>1 && r<map[i][j].length()) r = map[i][j].length(); } } return r; }

uniqueshivam + 0 comments int n = s.length(); int[] arr = new int[27];

`int max_size=0; int size=0; for(int i=0;i<n;i++) { arr[(int)s.charAt(i)-96]++; } for(int i=1;i<27;i++) { if(arr[i]!=0) { char first = (char)(i+96); for(int j=i+1;j<27;j++) { if(arr[j]!=0) { char second = (char)(j+96); StringBuilder sb = new StringBuilder(); size=0; loop: for(int k=0;k<n;k++) { if(s.charAt(k)==first) { if(sb.toString().length()==0) { sb.append(first); size++; } else { if(sb.toString().charAt(size-1)==first) { break loop; } else { sb.append(first); size++; } } } else if(s.charAt(k)==second) { if(sb.toString().length()==0) { sb.append(second); size++; } else { if(sb.toString().charAt(size-1)==second) break loop; else { sb.append(second); size++; } } } if(k==n-1) { System.out.println(sb.toString()); if(sb.toString().length()>max_size) max_size=sb.toString().length(); } } } } } } return max_size;`

anishagirisha + 0 comments YES

taytun + 0 comments [deleted]VictoriaB + 0 comments Or maybe a hint like 'brute force' (taking a cue from the editorial solution).

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

chervanev + 0 comments 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.

beastieric + 1 comment 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.

h0193250 + 0 comments Yea sorry I understand, in fact I use that solution ðŸ˜… sorry for asking I got confused, I was thinking in doing this for instead of letters using any number and doind that solution the code would be exponential in the bigger number you could get, any Idea?

citrin + 0 comments 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.

h0193250 + 3 comments 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?.

jhayne + 0 comments For each two-letter combination, you actually have to go through the length of the word which is <= 1000, so your worst case is actually 351,000 iterations

fnhckr + 0 comments O(C(n, 2)) is actually O(nÂ²) not O(n!) because C(n, 2) = n * (n-1) / 2

This gives an overall runtime complexity of O(mnÂ²) for the approach you described (alternating sequence test for each pair of letters), where m is the length of the input string and n the size of the alphabet.

To answer you question: you can bring it down to O(mn) at the cost of O(nÂ²) extra space. Some ways to do it are described here in the comment section.

r_i_v_a + 0 comments Depending on the input string, you might not even need to test every 2-letter combination -- you can get the frequencies of all letters on the first pass through the string, then not bother testing (a, b) if their counts are off by more than 1, or if they would add up to less than some candidate solution you already found.

h283074970 + 1 comment 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:)

nitika_kamboj92 + 0 comments Can you explain the logic?

gavin_qi + 0 comments but even brutal force can solve it

plmuon + 3 comments 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; } }

syz3r + 0 comments Instead of looping from 'a' to 'z' you can easily find distinct character in string using sets.

set<char> set; int size; cin >> size; string s; cin >> s; // find distint char for(char a : s){ set.insert(a); } int m = 0; if(s.length() > 1){ for( auto a : set){ for(auto b : set){ if(a == b) continue; int n = count_alternating(s,a,b); if(n > m) m = n; } } }

r_i_v_a + 0 comments You don't need to try all possible pairs of letters. You can get the count for each character in linear time (scanning through the string), and it doesn't make sense to test in detail 2 letters whose counts differ by more than 1.

ashishkapil + 0 comments Indeed a great answer, made me realised that it is really an easy question

vjvipulvj + 1 comment 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

Lisanaaa + 0 comments haha, be easy! Everything will be ok, just keep practice!

beckwithdylan + 0 comments 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)

Xeqtr92 + 0 comments doesnt need regex, simple o(n) solution exists.

hellomici + 0 comments 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

ayush199429 + 0 comments was hoping for this comment after reading the question.

zisikons + 0 comments 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.

williamng + 0 comments 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.

stempl + 0 comments Agree! I did in PHP but wasn't easy.

ipg_2016069 + 0 comments 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;`

}

Byte_24 + 0 comments i tottaly agree with u bro!!!

mulugurunaveen + 0 comments Yes.

pgmreddy + 0 comments **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.**ananraddad + 0 comments 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; }

uniqueshivam + 0 comments This question dosen't need regex at all, it is a very easy problem which can be solved with simple logic, loops along with using string builder (in java).

k_mouratidis + 0 comments This should be a reasonable solution, without regex:

from itertools import combinations def alternate(s): acceptable_solutions = [""] # Get all 2-letter combinations and iterate over them available_combs = list(combinations(set(s), 2)) for comb in available_combs: # remove characters not in in the set we are testing clean_str = "".join(char for char in s if char in comb) # checks if all pairs from (0,1) to (-2, -1) are not the same, if all(clean_str[i-1] != clean_str[i] for i in range(1, len(clean_str))): acceptable_solutions.append(clean_str) # get the len of each item and return their max return max(len(x) for x in acceptable_solutions)

kbalaji_uk + 0 comments True I don't think its easy atleast from C++ perspective, if anyone disagree on the same please let me know on how can this be done.

kris_tobiasson + 0 comments Here is my approach via JS. I just check each possible pair by splitting the rest of the characters out.

let c1; let c2; let longest = 0; for(let i = 0; i < s.length; i++){ if(s.indexOf(s.charAt(i)) === i){ c1 = s.charAt(i); for(let j = i + 1; j < s.length; j++){ let str = s; if(s.indexOf(s.charAt(j)) === j){ c2 = s.charAt(j); for(let k = 0; k < s.length; k++){ if(s.indexOf(s.charAt(k)) === k){ let c3 = s.charAt(k); if(c3 !== c1 && c3 !== c2){ let arr = str.split(c3); str = arr.join(``); } } } if(str.length > longest) { longest = getLengthIfValid(str); } } } } } return longest; function getLengthIfValid(str){ for(let i = 0; i < str.length - 1; i++){ if(str.charAt(i) === str.charAt(i+1)){ return longest; } } return str.length; }

venkatesh_16 + 0 comments [deleted]

Racsoth + 19 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.

jgdangelo + 1 comment 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!

Racsoth + 2 comments Thanks :) I came up with that solution by myself while analyzing the problem, so I don't know if it uses some kind of common technique. It may be some kind of Dynamic Programming, but I don't know because I haven't learned DP yet but only know its basic definition.

PortgasAce + 1 comment +1 for honesty

cs16mtech11005 + 0 comments can u please tell me where you the learn concepts of strings

alecoder + 0 comments It is simillar what we call DP Tabulation approach.

bnegrao + 1 comment i didn't understand anything about your solution.

RobertsN + 0 comments Basically what he did (and actually I also did) was to build a square array of size 26 (imagine columns a,b,c,d.. rows also a,b,c,d). Also a similar array initialized to zeros. For each letter in the string, check the corresponding row AND column for that letter. If the cell is empty or it is the other value (i.e. if checking columns take the row id and viceversa), update the cell with the char of the string being analized and add a +1 to the parallel count matrix. If it's the same value as the char being checked it means that between both instances of that char the other one isn't there (and I also mark the count matrix with -1).

Basically you're checking for alternations. For example if checking with 'a' you find an 'a' already in the cell for say row 'd' it means that between the previous 'a' and this one there has been no 'd' in the string so therefore 'a' and 'd' are NOT a valid pair of chars.

When you've finished traversing the string, simply find and print the biggest value in the count matrix. So as to not give it all away, there's an edge case to cater for (Test case #1).

Kot_Zadrot + 0 comments [deleted]Lucodivo + 5 comments 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; } }`

RodneyShag + 1 comment Great code. I have a small suggestion. There is no need to convert the String to a character array to iterate over it. You can alternatively loop through it like this by using s.charAt(i)

aravind1913 + 1 comment character arrays are more efficient than charAt() for iterating.

RodneyShag + 2 comments Interesting. Did you have a source that claims this?

aravind1913 + 0 comments [deleted]aravind1913 + 0 comments Well, it depends on your objective. If it's just 1 test case or a small value string, it doesn't make a difference. But in case of large values, it does make a difference. You can give it a trial. Anyways, a detailed description of the scenario is provided in this Stackoverflow post... https://stackoverflow.com/questions/8894258/fastest-way-to-iterate-over-all-the-chars-in-a-string

saurabhmishra221 + 3 comments My code is not clearing many testcases can you tell me why?

int maxLen(string s){ char alpha[26][26]; int value[26][26]; for(int i = 0 ; i < 26; i++){ for(int j = 0 ; j < 26; j++){ value[i][j] = 0; } } for(int i = 0; i < s.length(); i++){ int index = s[i] - 'a'; for(int j = 0; j < 26; j++){ if(alpha[index][j] != s[i] && (value[index][j] != -1)){ alpha[index][j] = s[i]; value[index][j]++; } else{ value[index][j] = -1; } if(alpha[j ][index] != s[i] && value[i][index] != -1){ alpha[j][index] = s[i]; value[j][index]++; } else{ value[j][index] = -1; } } } int maxlen = value[0][0]; for(int i = 0 ; i < 26; i++){ for(int j = 0 ; j < 26; j++){ if(maxlen < value[i][j]) maxlen = value[i][j]; } } if(maxlen> 0){ return maxlen; } return 0; }

vernwalrahul + 0 comments All seems good. Just make sure that alpha array don't have any garbage value. Better if you initialize it with ' ' or some non alphabets characters.

rchoudhary98 + 0 comments probably your test case is not considering the case where such a string can not be formed. u need to consider the case if maxlen <= 1 , u need to print 0.

sobankhan1144 + 1 comment change value[i][index] to value[j][index] in second if-statement and return 0 when string length is less than 2.

saurabhmishra221 + 0 comments thank you so much for the correction, i was doing this silly mistake :(

THE_black_jaguar + 0 comments [deleted]nive24071997 + 0 comments Great code. Here the output is the length of the string 't'. If i want to print the string 't', how the code will be?

clivic + 0 comments Well I think it's O(26n) time. 26 happens to be a constant here.

Yuanyen + 2 comments 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;`

}

rahulhacker + 0 comments Sorting itself would add some complexity to this approach. Would it actually be faster ?

fnhckr + 1 comment If i understand your getCount method correctly (you probably loop over the complete input string, right?) your algorithm actually is slower than Racsoth's.

The runtime complexity of your algorithm is O(mnÂ²) where m is the length of s and n the size of the alphabet. To see why think about the worst case: It happens when there is no valid t. Your algorithm will still check all O(nÂ²) letter pairs.

The algorithm of Racsoth has a runtime complexity of O(mn) because for each letter of the input string it only updates O(n) places, no matter how the letter frequencies are distributed.

However, if you slightly modify your code you get an algorithm with good average runtime complexity for random input (maybe even O(mn), I'm not sure). Consider the following sorted frequency distribution:

a b c d e 5 4 3 2 1

You only need to check the pairs: (a,b) (b,c) (c,d) (d,e)

This is because the frequency difference for any two letters must be smaller than 2 in an alternating sequence. Try it, you can not make an alternating sequence with 5 'a's and 3 'b's for instance.

callum_mcrae5 + 0 comments I took the same approach but the algorithm checks the difference in length of frequency of characters. I first count the frequency of each letter and put it in a multimap, with frequency as key and letter as value. I then double loop in descending order of frequency (which removes all other letters and then checks if the letters alternate), and only check frequencies that are less than or equal to 1 in difference. So for example:

24 > g 24 > p 23 > h 20 > x 18 > z 17 > v

In this example I would check g->p, g->h, p->h, and z->v. It would also break from the loop early if the highest length match is greater than the sizes of the 2 letters being matched plus 2 (you could also skip any letter combination checks that had a combined frequency that was equal or less than the previously matched length). So if I had a match with g->h, I would skip p->h and then break from the loop and not check z->v, because any other combination will always be a lesser length.

sayantan_dey_34 + 0 comments hi there

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

realq86 + 0 comments Very clever DP solution. The sub problems are the substrings of an input.

Aronzx + 0 comments This is one of the most beautiful piece of artforms.

iakshaygoyal + 0 comments awesome job buddy!!!

Mythili_P + 0 comments [deleted]ranjithvj + 0 comments Thanks for the explanation. I was able to solve the problem after looking at your logic.

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

NSHalex + 0 comments Great idea! Thank you.

vkokielov + 0 comments yep, that's the right way to do this...

anil_surmeli + 0 comments Here is the python solution for this algorithm:

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

crypter_dine + 0 comments 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.

clivic + 0 comments 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; }

siddhantvarma + 0 comments Super genius solution! Can someone please share the c++ code for this solution? I'm still having a hard time cracking every step and coding it down.

Harsh_Mandalgi + 3 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.

anupamsourav + 0 comments really, it was a very interesting solution, thanks a lot

vmikhailikov + 1 comment 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); }

vishaldugyala + 0 comments Since it's a string taking input itself is O(n).

PRO_BOY + 0 comments Thanks a lot for this.

samar19972102 + 1 comment I can't believe this has been labelled as 'Easy' ! Took me quite some effort to solve it correctly. Also, the number of submissions indicates the toughness of the problem. Without doubt, one of the hardest 'Easy' questions on hackerrank.

kssahoo + 0 comments My thought is also the same. This is defintely not easy.

Sort 683 Discussions, By:

Please Login in order to post a comment