- Practice
- Algorithms
- Strings
- Two Characters
- Discussions

# Two Characters

# Two Characters

smddzcy + 27 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 + 12 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 + 1 comment 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.

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

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.

sqqqqq23 + 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.

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

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 + 2 comments can u solve it in java?

BALYAM_muralidh2 + 4 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 + 0 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; }

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]

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

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.

Racsoth + 17 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 + 1 comment 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

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 + 4 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?

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.

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.

dr0opy + 4 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 ;)deathlessdragon1 + 2 comments 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

dr0opy + 0 comments you can take a string as a global or local variable ,it wont matter.only thing u need to do to check all possible pair of char between a-z

loganphanxnt1 + 0 comments with my codes: the result of your String is: 24

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

}

_yash_agarwal_ + 0 comments nice! you can use set container to identify unique elements.

viigihabe + 0 comments While on the optimization. There is still one more simple thing that can be made. While concatenating characters to a string you can check whether the pattern is broke allready:

if(h.empty())

`h += s[l];`

else

`if(h.back() == h[l]) { f = false; break; } else h += h[l];`

And if one writes C++ one should use bool not an int as a boolean, it is misleading otherwise. Nevertheless - move the declaration of "f" above that for-loop and you can elliminate the next loop following.

Alpha__killer + 2 comments what a problem to check only those charcter which are present in inputed string?

dr0opy + 0 comments @Alpha_killer(Aryan raj) didn't understand your question?

Silver_Shark + 1 comment @Alpha_killer ..actually it reduced a lot of time by only checking the characters in input string rather than checking all the alphabetical combinations.

Alpha__killer + 0 comments yup

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

zhenyakornev + 0 comments To Hackerrank @admin, I think it is better to take the task-scoring model from resourse like acm.timus in where the difficuly is calculated based on the number of people actually solved it. or maybe as a ratio of solved/attempt. By now, there are a lot of examples where some tasks are easy as hell and give you 30 points and whereby some like this one not such easy for 15 points.

3Murthi + 0 comments Little bit confusion but I got it with a simple logic.

def alternate(s): x=set(s) m=0 l=list(map(set,combinations(x,2))) for i in l: y=x-i z=s for j in y: z=z.replace(j,"") r=("".join(i))*(len(z)//2) if r+r[0]==z or r==z or r==z[::-1] or r[1]+r==z: m=max(m,len(z)) return m

- Let me know if have any doubts regarding my code.

RodneyShag + 3 comments ### Java solution - passes 100% of test cases

From my HackerRank solutions.

Time Complexity: O(n) with just 1 traversal of our String

Space Complexity: O(1)There are approximately 26^2 possible combinations of alternating pairs of letters. Notice that this number remains constant and is not dependent on the length of our input String. This fact will help us achieve a linear O(n) runtime.

We want to solve this problem with just 1 traversal of our String, so we solve all 26^2 subproblems simultaneously. We use two int[26][26] arrays to keep track of the 26^2 solutions.

As we iterate through our String, we update our two int[26][26] arrays as follows:

- int[26][26] letter: This array is used to keep track of which of the alternating characters we saw last. To achieve this, for the current character
*ch*, we update the corresponding row (26 entries) and column (26 entries) with the (ASCII) value of "ch". - int[26][26] count: if we find that no solution exists for a pair of characters (which happens when the characters don't alternate), we store -1 in this array. Otherwise, we store he current maximum length of
*s*for the pair of characters.

Our final answer is the maximum value in

*int[26][26] count*import java.util.Scanner; public class Solution { public static final int NUM_LETTERS = 26; public static void main(String[] args) { /* Save input */ Scanner scan = new Scanner(System.in); int length = scan.nextInt(); String str = scan.next(); scan.close(); /* Edge case */ if (length <= 1) { System.out.println(0); return; } /* Create arrays representing the 26^2 subproblems */ int [][] pair = new int[NUM_LETTERS][NUM_LETTERS]; int [][] count = new int[NUM_LETTERS][NUM_LETTERS]; for (int i = 0; i < length; i++) { char letter = str.charAt(i); int letterNum = letter - 'a'; /* Update row */ for (int col = 0; col < NUM_LETTERS; col++) { if (pair[letterNum][col] == letter) { count[letterNum][col] = -1; } if (count[letterNum][col] != -1) { pair[letterNum][col] = letter; count[letterNum][col]++; } } /* Update column */ for (int row = 0; row < NUM_LETTERS; row++) { if (pair[row][letterNum] == letter) { count[row][letterNum] = -1; } if (count[row][letterNum] != -1) { pair[row][letterNum] = letter; count[row][letterNum]++; } } } /* Find max in "count" array */ int max = 0; for (int row = 0; row < NUM_LETTERS; row++) { for (int col = 0; col < NUM_LETTERS; col++) { max = Math.max(max, count[row][col]); } } System.out.println(max); } }

Let me know if you have any questions.

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

RodneyShag + 0 comments Your repo looks great!

KeyurPotdar + 1 comment 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?RodneyShag + 1 comment Writing 26 every time is a little unclear if it's not obvious that it stands for 26 letters in the alphabet. Generally, for any number other than 0 or 1, you should use a variable for it if you are going to be using it multiple times so that others know what the number stands for.

KeyurPotdar + 0 comments Got it. Thanks for the response. :-)

AnonymousNovice + 1 comment Good solution :)

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

RodneyShag + 1 comment Hi. Thanks. There may be a way to get rid of 1/2 the table entries by doing what you suggested. That won't speed up the runtime, but it will save on space. The space complexity will still be O(1), but it will use half as much space.

AnonymousNovice + 1 comment No doubt, your solution is elegant. Now i am thinking, could we utilize property of this 2- D table in telling which sequence is occured in original string like was it aba or bab (means could it be filled in some smarter way to preserve ordering.)

What do you think ?

RodneyShag + 0 comments I can't think of any to do this that doesn't obscure the code. Making the code easier to understand by using the entire 2-d array is more important than saving some space, in my opinion.

- int[26][26] letter: This array is used to keep track of which of the alternating characters we saw last. To achieve this, for the current character

sein_tao + 2 comments As the number of combinations of letters are <= 26 * 25 / 2 and len(s) <= 1000, It is not needed to optimize the code, is it?

#!/bin/python3 from itertools import combinations def meet_pattern(s): return all(s[i-1] != s[i] for i in range(1,len(s))) s_len = int(input().strip()) s = input().strip() letters = set(s) max_len = 0 for pair in combinations(letters,2): substr = "".join(i for i in s if i in pair) if meet_pattern(substr): max_len = max(max_len, len(substr)) print(max_len)

JB555 + 2 comments 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. :)

Mr_ayushgoyal + 1 comment I would like to see your solution too.

JB555 + 0 comments Here is the code I was mentioning:

#!/bin/python3 import re from itertools import combinations s_len = int(input().strip()) s = input().strip() def isValid(s, a, b): regex1 = a + a regex2 = b + b regex3 = r"[^" + a + b + r"]+" if (re.search(regex1, s) or re.search(regex2, s) or re.search(regex3, s)): return False else: return True max = 0 for p in combinations(set(s), 2): s2 = "".join(x for x in s if x in p) if isValid(s2, p[0], p[1]): if len(s2) > max: max = len(s2) print(max)

scientistpratap1 + 1 comment Can anyone please help me understand what really regex is ?? Is it regression??

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

sein_tao + 1 comment The initialization of Counter need to read the whole list. So it may not able to beat the simple iteration solution. Did you test it yet?

msram + 0 comments I tested it and it's faster than the simple iterative solution. The Counter initialization is a one time task. The part that constructs t and checks if t meets the required criterion is also O(n) and, without checking the counts, it would run for n*(n-1)/2 times (where n = len(s)). Checking the counts before doing all this would avoid that O(n) operation, when unnecessary. The overall running time is therefore less with the Counter based logic.

Sort 583 Discussions, By:

Please Login in order to post a comment