tao_zhang Mine in Java
import java.util.Scanner; public class RemoveDuplicateLetters { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String str = scanner.next(); for (int i = 1; i < str.length(); i++) { if (str.charAt(i) == str.charAt(i-1)) { str = str.substring(0, i-1) + str.substring(i+1); i = 0; } } if (str.length() == 0) { System.out.println("Empty String"); } else { System.out.println (str); } } }
Stef2k15 Thanks for that i = 0 :) Had basically the same code, but I couldn't think of an easy solution to go back to the beginning of the string again after deleting a pair of letters, even if it was that easy...
I used StringBuffer instead of String. Isn't it more efficient, cause less objects are created? I'm really not sure about that, some feedback would be appreciated. Here my code:
public static void main(String[] args) { Scanner stdin = new Scanner(System.in); StringBuffer s = new StringBuffer(stdin.nextLine()); for(int i = 1; i < s.length(); i++) { if(s.charAt(i) == s.charAt(i-1)) { s.delete(i-1, i+1); i = 0; } } if(s.length() == 0) System.out.println("Empty String"); else System.out.println(s); } }
tao_zhang You are right, I think yours perfomance would be better than mine. But just FYI, as far as mutables go, StringBuilder is faster than StringBuffer (because StringBuilder is not synchronized). General rules are not to use StringBuffer if only one thread is involved. Because lots of locking and unlocking code for synchronization will unnecessarily take up CPU time.
Stef2k15 Ok. Thanks for your answer! I'll keep that in mind next time.
shraddhashrivas1 Thanks for pointing out about the locking /unlocking thing. :)
vaibhav31595 mam but it shows an compilation error says s is string type and you use delete function which gives u an integer??
ujjawaljaiswal21 Thank you for the advice on unlocking and locking.
ranjithkumar2811 public class Solution {
public static void main(String[] args) { Scanner in = new Scanner(System.in); StringBuilder s = new StringBuilder(in.nextLine()); for(int i=1;i<s.length();i++) { if(s.charAt(i)==s.charAt(i-1)) { s.delete(i-1,i+1); i=0; } } if(s.length()==0)System.out.println("Empty String"); else System.out.println(s); }} using string builder
spartacus5552 [deleted]
nm1511 Jeez. and here I am compiling a regex pattern and using Matcher when a plain ol' String and for loop would have worked just fine.
siddhantsatkar I used recursion but doing i=0 is so elegant and clean.
krish258 true, it just makes the solution so readable.
tadavartisujith How did you do using recursion ?
Monkeyanator Have recursive function that:
1) Check if string can be reduced. If not, return string 2) If it can, trim the first part that can be reduced, and return it back to the same function.
sarrost I did mine in python, however my solution is messy as hell especially since I ended up reaching the max recursion in the one test case with one of the larger strings.
I ended up having to split strings into substrings, cat them and check if that string was reduced again, rinse and repeat.
But the main idea I had was to use 2 recursive functions, one which did the reducing and one that checks if the string is reduced, the rest is in code.
def reduce_str(s, index): """ reduces the string recursively """ last_index = len(s) - 1 if (len(s) == 0): return 'Empty String' if start >= last_index: if is_reduced(s, 0): return s else: return reduced(s, 0) elif s[index] == s[index + 1]: if index + 1 < last_index: return reduced(s[:index] + s[index + 2:], index) elif end == last_index: return reduced(s[:index], index) else: return reduced(s, index + 1) def is_reduced(s, index): """ checks if the string is reduced, returns a bool """ last_index = len(s) - 1 if start == last_index or len(s) == 0: return True elif s[index] != s[index + 1]: return is_reduced(s, index + 1) else: return False
tricerabottoms It might perform the task adequately, but it uses excessive amounts of continuous stationery. We can save the planet if we all write in Perl! Observe:
$_=<>;2while+s;(.)\1;;g;print$_||'Empty String';
pialgi goodluck_deciphering, #if_it_was_difficult_for_me_i_make_it_difficult_for_everyone, #look_how_smart_i_am
jyiyao if i!=0, making i=i-1 will be efficient.
Ankur_Beginning will you pls explain why you are deleting i-1 and i+1 element
Tutankhamun it's i-1 up to (but not including) i+1. So i-1 and i are deleted
aldoinfanzon This solution is very nice and clean good work
vnspriyanka476 I have one doubt. If chars at i and i-1 position are equal, then they both have to be deleted. But according to your program, chars at i-1 and i+1 position will gets eliminated. Please dont mind and give me clarification on this.
Ausaf [deleted]
ishabandi charAt i and i-1 are same. So you need to delete both of there characters. The method: String.delete(int startindex, int endindex)
Here, startindex is included and endindex is excluded. That is, the charachters from startindex to endindex -1 will be deleted.
So the method will only delete i-1 th char if s.delete(i-1,i) is used. Hence, s.delete(i-1,i+1) is used which will delete all the charachter from i-1 to i.
I hope this helps.
deveshmodale thanks
sagupta8399 ishabandi I got to know about a new function String.delete(startindex,endindex) in which startindex is included and endindex is excluded. Thanks :) Can you tell me a good source where all important string functions are mentioned.
vaibhav31595 mam but it shows an compilation error says s is string type and you use delete function which gives u an integer??😢😢please help me out...
jagacode i cant understand why that i=0 is used for ...can u explain me?
neelkusum93 i is used because it brings the pointer to the beginning of the string .The checking for similar alphabet has to be done with a character whose index is 1 with a character whose index is 0. If 'i=0' is avoided then we do not get an efficient solution as it starts printing the duplicate letters as it is. Hope it helps!
BALYAM_muralidh2 for(int i =0;i<s.length();i++){ for(int j =0;j<=s.length()-2;j++){ if(s.charAt(j) == s.charAt(j+1)){ String newString = removeChar_At(s,j); s = newString; j = 0; } } } if(s.equals(null)||s.equals("")){ return "Empty String"; } return s; } public static String removeChar_At(String s,int pos){ return s.substring(0,pos)+s.substring(pos+2); }
BALYAM_muralidh2 i = 0(because u have to check the string from the start as their indexes are getting changed because u are creating new string everytime )
divs4debu public static void main(String... args) { Scanner stdin = new Scanner(System.in); StringBuffer s = new StringBuffer(stdin.nextLine()); for(int i = 1; i < s.length(); i++) { if(s.charAt(i) == s.charAt(i-1)) { s.delete(i-1, i+1); if( i-1 > 0) i = i-2; else i = 0; } } if(s.length() == 0) System.out.println("Empty String"); else System.out.println(s); }
We can also do this?
winty95 In my solution result.delete(i-1, i+1); i-=2; if(i<0) i=0; Our performence might be better just i=0.
maheshvangala191 with out taking i=0 i am getting runtime error as StringIndexOutOfBounds so i enclosed my code in try block and i got the answer
gokulYadav i too implemented the same but stuck in loop thanks for zero
gsjohal why are you doing it from i-1 to i+1? can you please explain?
spartacus5552 Why i=0 ... it should be i=1 as "s.charAt(i-1)" will be "s.charAt(-1)".
abhishek1810 Why you are making i=0; even though it works if you dont make i=0.
Thanks in advance..
Stef2k15 It's not working without i = 0 for me.
Every time you delete a pair of letters, you create a new String. So you have to restart at the beginning of the new string to find potential new pairs.
Example: baab
Without the i = 0, you will delete the letters "aa". The new string is "bb", but you won't delete those two letters cause your loop is already done.
NiceBuddy try this way: C++14
#include <string> #include <iostream> std::string super_reduced_string(std::string &s) { for(std::size_t index=1; index < s.size(); ++index) if(s[index-1]==s[index]) { s.erase(index-1,2); index=0; } return s.empty() ? "Empty String": s; } int main() { std::string s; std::cin >> s; std::cout << super_reduced_string(s) << std::endl; return 0; }
Kanna_19 [deleted]
alvin_ega93 Everytime a pair of letter deleted, the loop must be restarted to delete another pair until there are none consecutive duplicate character.
Remember after the loop we increment variable i with 1, so we have i=0 to return to its original position which is 1.
rvrishav7 not necessary.. if u bring pointer (say i) to a previous value after deleting
kdishashetty2992 This comment helped me actually understand why i=0;
neelkusum93 It does not work efficiently in the later cases when you add double letters. Those double letters get printed in the output. It is important to get the pointer right at 0 index after any reduction is done on the string.
divs4debu public static void main(String... args) { Scanner stdin = new Scanner(System.in); StringBuffer s = new StringBuffer(stdin.nextLine()); for(int i = 1; i < s.length(); i++) { if(s.charAt(i) == s.charAt(i-1)) { s.delete(i-1, i+1); if( i-1 > 0) i = i-2; else i = 0; } } if(s.length() == 0) System.out.println("Empty String"); else System.out.println(s); }
We donot require to do i = 0 everytime just when deleteing starting pair
abhi_chawla96 what is the use of if(i-1>0) i=i-2 ??
mca_amit89 i am trying solve this code but I did not please clarify why delete used and its not support which version is working.
wkusnierczyk You might want to research a bit on the complexity of joining strings in java, and how it scales. (It doesn't.)
tao_zhang I agree StringBuilder and StringBuffer [both amortized O(n)] have better perfomace than string concanation [O(n^2)]. I just didn't modify my solution because of laziness.
GokayH Actually, if you use string concatenation in any way (whether it be using String, StringBuilder or StringBuffer), there is no way to get O(N) performance for this problem. You have to somehow "mark" the deleted characters and use custom iterators for O(N) performance
vmalakhin Or just build new string symbol by symbol
public static void main(String[] args) { final String str = new Scanner(System.in).next(); final char[] chars = new char[str.length()]; int c = 0; for(int i = 0; i < str.length(); i++) { final char nextChar = str.charAt(i); if(c > 0 && nextChar == chars[c - 1]) { c--; continue; } chars[c++] = nextChar; } System.out.println(c == 0 ? "Empty String" : new String(chars, 0, c)); }
ajeet_meena We can use linked list for o(n) time complexiety. Guide me if I am wrong.
vmalakhin could work but stack makes more sense especially if it's array based.
ajeet_meena Exactly, Stack is the answer. I wonder why people here are managing strings or writing regex.
vmalakhin that's really good question.
silja_tirronen I agree. It is not necessary to iterate over the string multiple times or construct intermediate results. Surprisingly few people tried the stack approach. Here is my solution in Java.
public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String s = scanner.next(); System.out.println(reduce(s)); } private static String reduce(String s) { Stack<Character> stack = new Stack<>(); int h = 0; //height of stack for (int i=0; i<s.length(); i++) { if (!stack.isEmpty() && stack.peek().equals(s.charAt(i))) { stack.pop(); //throw away h--; } else { stack.push(s.charAt(i)); h++; } } if (h == 0) { return "Empty String"; } //at the end, stack holds reduced string in reverse order. char[] reduced = new char[h]; for (int i=h-1; i>=0; i--) { reduced[i] = stack.pop(); } return new String(reduced); }
sleepyhollow [deleted]sleepyhollow [deleted]sleepyhollow This is a really good solution. Some languages do not allow modifying the iterable while looping on it. Awesome!
atishayjain708 It is only for solutions such as this that I read discussions. Submitted a simple iterative solution. Would've never thought stack would be better!
kaustav3 I've a similar approach in C#
static string super_reduced_string(string s) { Stack<char> stack = new Stack<char>(); foreach (char c in s) { char top = (stack.Count==0)?' ':stack.Peek(); if (top == c) stack.Pop(); else stack.Push(c); } char[] reduced = stack.ToArray(); Array.Reverse(reduced); if (reduced.Length ==0 ) return "Empty String"; else return(new String(reduced)); }
prutnara Thank you kaustav
yklyuyev Used your idea in Python:
def super_reduced_string(s): res = [] # stack for c in s: if res and res[len(res)-1] == c: # peek what's on top res.pop() else: res.append(c) res = ''.join(res) return res or 'Empty String'
Easier to read comparing to perl, hu?
jaco0797 How can both res and res[val] == c? doesn't res include the entire list while res[val] is a single letter & c is a single letter?
_SleepyOwl this confused me for a bit too, but take a look at the syntax again. the syntax is saying, if res is true and res[len(res)-1]==c is true, then the equality is true.
more concretely, here is another example
if 5 and 4 == 4: print ("True") #This prints True
5 is always true as it is not compared to anything, thus the equality will always return true so long as 4==4
in this problem, res will always be true so long as it is not an empty list.
kukanishka why can't it be only if res[len(res)-1] == c
liam_kirsh If the stack is empty, len(res) will be 0, so len(res) - 1 will be an index of -1. Trying to access an index in an empty string causes an "IndexError: string index out of range" in Python.
kukanishka why can't it be only if res[len(res)-1] == c??
liam_kirsh Great solution. For more readability, you can use negative sequence indices in Python to specify an offset from the end of the stack, like so:
def super_reduced_string(s): res = [] for c in s: if res and res[-1] == c: res.pop() else: res.append(c) res = ''.join(res) return res or "Empty String"
tim_mathias Nice solution. I've optimised it a bit so that we don't have to reverse the reduced string at the end by iterating through the original string in reverse order. This results in the stack being in forward order. Then a simple concatenation of the stack gives us the reduced string.
static string SuperReducedString(string s) { Stack<char> stack = new Stack<char>(); for (int i = s.Length - 1; i >= 0; i--) { char c = s[i]; if (stack.Count > 0 && stack.Peek() == c) { stack.Pop(); } else { stack.Push(c); } } return stack.Count > 0 ? string.Concat(stack) : "Empty String"; }
satummal Neat...
srinidhi_343 For the String aaabcccdddb the expected output would be abcd , but the stack approac is giving us abcdb I guess we need to lookinto the contents of the stack again.
taciosd Actually,
abcdbis correct. The twobletters left in the string are not next to each other, so this is the final reduced form of the original string.
gps_gaurav u can use array for O(n) complexiety.
Shady_Shah What does i=0 do here exactly?
VARIK since the for loop is starting from i=1, making i=0 makes sure the next time the for loop runs from the firts index.
kvpratama My java solution
Scanner s = new Scanner(System.in); StringBuilder input = new StringBuilder(s.next()); for(int i = 0; i < input.length()-1; i++){ if(input.charAt(i) == input.charAt(i+1)){ input.delete(i, i+2); if(input.length() == 0){ input.append("Empty String"); break; } i = (i==0) ? -1 : i-2; } } System.out.print(input);
candy_154 i = -1 is sufficient
vasukapil2196 can you explain how i = (i==0) ? -1 : i-2; works?
pnenad38 int i; if(i == 0) i = -1; else i = i - 2;
karadeniz Any reason using SubString over Remove? Is there a big performance difference between those?
sharan281 hi, just wanted to know why char i and char i-1 are compared instead of chari and char i+1(intializing i to 0 in for loop)
lucas2213690 I improved your code, it's a better choice use StringBuilder to delete, cause Strings is immutable in Java
import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) { Scanner n = new Scanner(System.in); String s = n.nextLine(); for(int i = 1; i < s.length() ; i++){ if (new Character(s.charAt(i)).equals(new Character(s.charAt(i -1)))){ s = new StringBuilder(s).deleteCharAt(i).deleteCharAt(i -1).toString(); i = 0; } } String response = (s.isEmpty()) ? "Empty String" : s; System.out.println(response); } }
bpalaciosa Thank you
manikesh_verma This is not correct.. it removed b as well
K1408442 [deleted]
saif01md Why is this code wrong ?
for(int i=0;i<s.length();i++){ if(s.charAt(i)==s.charAt(i+1)){ s=s.substring(0,i)+s.substring(i+2); i=0; } }
raznaot maybe try s.length()-1 ? looks like charAt(i+1) would be out of range
smudassir719 initialize i = 1 in for loop
Hacker_RK because you have specified s=s.substring(0,i)+s.substring(i+2); in case when i will be equal to s.length-1 then in that case i+2 will be an out of range value.
Sanjay2293 instead of i=0, write i=-1; if we do i=0, then for next iteration, it will become i=1 and hence out of bounds.
ishansrivastava1 one doubt can u plz clear it ,there is nowhere mentioned to remove duplicate letters so why r u removing duplicate ones
[deleted] I don't understand the question apparently. Your code checks only letters next to eachother but does not account for pairs seperated by other single characters. There is no mention that pairs of letters will always be each other so we should be expecting something like "abcad" and should return "bcd" right?
Am I misunderstanding the question or are the test cases just incorrect?
Ausaf it should return abcad as u have to remove only adjacent pair of letters if they r same
AnonymousNovice Thank You for teaching something valuable.
jagacode i cant understand why that i=0 is used for ...can u explain me?
raghav_prakash Because while removing pairs, you might get some element from the beginning matching one at the end ending up as another pair. So he starts from the beginning to be safe and correct to eliminate all possible occurrences of pairs without having to resort to multiple loops. Also he's regularly updating the same string used for comparison. So he starts from the beginning to its length always to check if any pairs occur. When a string occurs such that from i = 0 to s.length() no pairs occur that string is finally the required string. The loop terminates and the string is returned (or "Empty String" if the resultant s.length() == 0)
raghav_prakash Wow! Very simple and efficient. But I would suggest using StringBuilder instead of string for faster I/O.
But wow....a great solution. Thanks a lot!
RickyCaoCao Good solution but I think using StringBuilder will save us from a lot of String Object creations.
avanii247 for(int i=0;i<(s.length()-1);i++) {
if(s.charAt(i)==s.charAt(i+1)) { s=s.substring(0,i)+ s.substring(i+2); i=0; } } if(s.length()==0) { return "Empty String"; } else { return s; } }I did something similar but this doesn't work for the testcase "baab" - It prints bb instead of printing Empty String. Could you help me please?
Time_Maker use for(int i=0;i<(s.length());i++)
avanii247 My if statement if(s.charAt(i)==s.charAt(i+1)) will throw an out of bound exception
pd121193 reinitialize i=-1 and not i=0 because once everything in your for loop is executed i is incremented changing i to 1 from 0. Hope that helps.
kumardivyankk36 int main() { string s; cin>>s; int i=0,l=s.size(); while(i
after i=0 executes in your code, the value of i becomes 1 as i++ executes
twitu Actually you don't need to make i=0 for each pair you find. In the worst case this will make the programme traverse the string again. Instead a better assignment would be i=i-1. this is the most optimized assignment because if any new pairs are formed due to removal of the current detected pair it will be at position i-1 and i-2. Example:
....i-2 i-1 i i+1.... ....b a a b......
after removing
....i-2 i-1.... ....b b.....
rbborneo This seems little inefficient going back to index 0 everytime you delete something?
[DELETED] [deleted]pep1439 used recursion:
static String super_reduced_string(String string, int startIndex){ if(string.length() == 0) return "Empty String"; else if(string.length() == startIndex + 1) return string; if(string.charAt(startIndex) == string.charAt(startIndex + 1)) { return super_reduced_string(string.substring(0, startIndex) + string.substring(startIndex + 2), --startIndex < 0 ? 0 : startIndex);//avoid negative index } else { return super_reduced_string(string, ++startIndex); } }
purvashah98 Hats off to your code! It is very neat.I was stuggling for the for loop condition since the last character wasn't going through the evaluation process. Thank you!
sankalp29 why should we run the loop till length of the string and why not length-1 because when te value of i reaches l-1 that is itself the last element of the string so will the substring(i+1)not give any garbage value?
tecnocratay great solution
dixitpranshu99 Please explain why do you write "i=0" in the if condition.
balgabekov1 def super_reduced_string(s): if not s: return 'Empty String' stack = '' for i, c in enumerate(s): if stack and stack[-1] == c: stack = stack[:-1] else: stack += c if stack: return stack return 'Empty String'
Shobith_ak could u please explain why i=0? I did not get that point
anuragtripathiit can u explain for baab will it not go array index out of bond
DasShubhadeep Simple implementation in C using stack in O(n) time. Do ask for any clarifications.
#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> int main() { char string[101]; scanf("%s",string); //printf("%s",string); char *stack=(char *)malloc(sizeof(char)*strlen(string));int top=-1;
for(int i=0;i<strlen(string);i++){ if(i==0) stack[++top]=string[i]; else { if(stack[top]==string[i]) top--; else stack[++top]=string[i]; } } if(top==-1) printf("Empty String"); else { for(int i=0;i<=top;i++) printf("%c",stack[i]); } return 0; }Yoam13 Please Explain Your Code...
DasShubhadeep Logic is as follows: 1. Add first character to stack 2. if last element added in stack(element in TOP) is same as next character scanned then it means two elements are adjacent so we pop. This removes adjacent same characters. 3. The characters remaining in stack are your reduced string.
the_dickhead well done bro .....it made me think differently..and being a C user i was getting a hell of time....
DasShubhadeep Thanks.
positivedeist_07 The time complexity is O(n), i think?? n being the number of characters of string. Excellect solution. But what about space? Here its O(n), n being the size of stack. Is it possible to solve in C using O(1) space?
DasShubhadeep Yes. It is definitely possible but time complexity may increase. I will comment here if I come to know of any simpler methods using o(1) space.
positivedeist_07 Yeah sure, time complexity will increase in that case. Btw, elegant coding and interesting thinking on ur solution :)
Hemanth_jain please explain ur code!
DasShubhadeep Logic is as follows: 1. Add first character to stack 2. if last element added in stack(element in TOP) is same as next character scanned then it means two elements are adjacent so we pop. This removes adjacent same characters. 3. The characters remaining in stack are your reduced string.
ProgramForFuture Mine LOL I know there is a better way but lets just put this for now.
#include <math.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <assert.h> #include <limits.h> #include <stdbool.h> void rm(char *s); char* super_reduced_string(char* s){ int len = strlen(s); int i; for(i = 0; i < len; i++){ if(s[i] == s[i-1]){ s[i] = s[i-1] = '$'; rm(s); len = strlen(s); i = 0; } } return s; } int main() { char* s = (char *)malloc(512000 * sizeof(char)); scanf("%s", s); int result_size; char* result = super_reduced_string(s); if(!strlen(result)) printf("Empty String\n"); else printf("%s\n", result); return 0; } void rm(char *s){ int len = strlen(s); int i, j; j = 0; for(i = 0; i < len; i++){ if(s[i] != '$'){ s[j++] = s[i]; } } s[j] = '\0'; }
jluisg_23 Here is my approach. Maybe more complexity, but it's a modular version. Any comments are welcome:
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> #define LENGTH 100 char* reduce_string(char* s) { int i, r_len, len = strlen(s); bool found = false; char* red_str; for(i = 0; i< len-1; ++i){ //Looking for repetitions if(s[i] == s[i+1]){ found = true; break; } } if(found){ r_len = len-2; if(r_len == 0) return NULL; } else{ return s; //r_len = len; //i = len; } //Replacement red_str = (char*)malloc(len*sizeof(char)); int k = 0; for(int j = 0; j < len; ++j){ if(j != i && j != i+1){ red_str[k] = s[j]; ++k; } } return red_str; } char* super_reduced_string(char* s){ char *sup_red, *str_tmp; do{ str_tmp = s; sup_red = reduce_string(s); s = sup_red; }while(str_tmp != s && s != 0); return sup_red; } int main() { char str[100]; char* str_red; char* str_test; scanf("%s", str); str_red = super_reduced_string(str); if(str_red == 0) printf("Empty String\n"); else printf("%s\n", str_red); return 0; }
adamk117 This is an elegant solution =)
prajyotkoli1 Nice logic...
kodomass string str; cin >> str; int i=0; while(i < static_cast< int > (str.size()-1)) { if(i>-1 && str[i] == str[i+1]) { str.erase(i,2); i--; } else i++; } if(str.empty()) cout << "Empty String" << endl; else cout << str << endl;
sridharjajoo thnx!..it really helped
kishore95cod thanks a lot bro
sdaqiq0 I was half way through doing this but got lost some where in the middle :(
vtovmasyan while(i < static_cast< int > (str.size()-1)) { if(i>-1 && str[i] == str[i+1]) { str.erase(i,2); i--; } else i++; } string::iterator it = adjacent_find(s.begin(), s.end()); while (it != s.end()) { s.erase(it, it + 2); it = adjacent_find(s.begin(), s.end()); }f2014411 Why are we using i > -1 and i--? Can we not simply do it without using it?
karajrish while(i < static_cast< int > (str.size()-1))
Can someone explain me what does this line do?
fstanley str.size() returns an (unsigned int). If you want to compare a signed int (int i) to an unsigned int (str.size()), you should use static_cast<> to tell the compiler to convert the unsigned int to an int before comparing.
andreox Isn't it better to use str.length() ?
krishnakeshav Nope, since both will have diffferent functionalities in this case.length() will only return for initial string whereas size keeps changing.
fstanley Sorry, this is wrong. STL string size() and length() are synonyms. They will always return the same value.
krishnakeshav aah..yes...apparently both of them shows same behaviour. I was missing static cast on length()
nkit1997knw Can't we use just (int) instead of static_cast
abyl_ikhsanov Nope, you can compare unsigned int to signed int in this case as length() is always > 0, so casting via static_cast, which is almost always a bad practice, is simply not neccesary.
Crystal_star can't we use "unsigned int i" instead.?
bhavya_it16 [deleted]isanrivkin [deleted]
juaxix interesting, I did something weird and longer but fun :)
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <cassert> using namespace std; template< typename... Args > std::string string_sprintf( const char* format, Args... args ) { int length = std::snprintf( nullptr, 0, format, args... ); assert( length >= 0 ); char* buf = new char[length + 1]; std::snprintf( buf, length + 1, format, args... ); std::string str( buf ); delete[] buf; return std::move(str); } void replaceAll( string &s, const string &search, const string &replace ) { for( size_t pos = 0; ; pos += replace.length() ) { // Locate the substring to replace pos = s.find( search, pos ); if( pos == string::npos ) break; // Replace by erasing and inserting s.erase( pos, search.length() ); s.insert( pos, replace ); } } int main() { string S, letters; cin>>S; for(int i=0; i<S.length(); i++) { if(count(letters.begin(),letters.end(),S[i])==0) letters+=S[i]; } //cout << "-"<<letters<<"-"<<endl; bool keepLooking = true; string w; while(keepLooking) { bool change = false; for(int i=0; i<letters.length(); i++){ w = string_sprintf("%c%c",letters[i] , letters[i]); //cout << "--" << w << "--" <<endl; if(S.find(w)!=string::npos) { replaceAll(S, w, ""); change = true; } } if(!change) keepLooking = false; } if(S.empty()) cout << "Empty String"; else cout << S; return 0; }
comments please?
gugigor too long, feels like the obfuscated Python Hello World except it's not obfuscated
kavyasree42 i have a doubt... if(i>-1 && str[i] == str[i+1]) i didnt use i>-1 but solved the challenge. what is the significance of i>-1
shulomithii26 why i++ again ?
craig_holland Simple Python/Regex solution:
import re s, regex = raw_input().strip(), re.compile(r'(\w)(\1)') match = regex.search(s) while match: s = s.replace(match.group(),'') match = regex.search(s) print s if s else 'Empty String'
ThundercloudABM I like your backref solution. Here's a ruby spin on your theme:
s = gets.strip s.gsub!($~.to_s, '') while s.match(%r{(\w)(\1)}) puts s.empty? ? 'Empty String' : s
hacker_bre I am confused on
re.compile(r'(\w)(\1)')
Would you mind provide some info or comments?
ThundercloudABM \1is a regex backreference.The backreference placeholder
\1is substituted with the substring that matches the group 1 pattern (\2is for group 2, etc).Their use is maybe a little more obvious when used with
replace/sub, where you not only want to find a pattern but also add to it or alter it; for example find all'b'or'f'and put arrows around them:re.sub(r'([bf])', r' ->\1<- ', 'abcdef') # 'a ->b<- cde ->f<- '
So, given string
'abbc'and patternr'(\w)(\1)':- Group 1 contains
(\w), which matches'a', so\1now becomes'a'and the regex will only be true if the next char is also'a'. - The next char is
'b'so regex gives up on'a'and looks for something else that matches\w, - This time
(\w)matches'b', and\1becomes a'b'; since the next character in the string is also a'b'the regex is satisfied, it stops searching, and returns'bb'.
- Group 1 contains
inxcess Super simple Python 2 solutions:
def removeRepeats(S): LS = list(S) i = 0 while i < len(LS)-1: if LS[i]==LS[i+1]: del LS[i] del LS[i] i = 0 if len(LS) == 0: print 'Empty String' break else: i+=1 return ''.join(LS)
charzard I like this solution, though when I ran it, it was quite slow and the compiler gave me the following message on two test cases: "Terminated due to timeout"
Was it just me, or did you also get this msg?
JB555 fyi: I had a very similiar approach (basically the same) and didn't have a time issue
amolkavitkar_19 change i+=1 to i = i+1 it will work below is my program it works fine:
!/bin/python
import sys
str_new = list(raw_input().strip())
if (len(str_new)>100)|(1>len(str_new)): sys.exit(1)
i =0 while i <(len(str_new)-1): if str_new[i] == str_new[i+1]: del str_new[i] del str_new[i] i = max(i-1,0) if len(str_new) == 0: print "Empty String" break else: i=i+1 else: print "".join(str_new)
sachinxlr try this
def super_reduced_string(s): m=list(s) c=0 while c<len(m)-1 : if m[c]==m[c+1]: del m[c] del m[c] if c!=0: c=c-1 else: c=c+1 if len(m)==0: return 'Empty String' else: return ''.join(map(str,m)) s = raw_input().strip() result = super_reduced_string(s) print(result)
fk2224 Here is mine:)
def super_reduced_string(s): # Complete this function t=list(set(s)) count=1 while count!=0: count=0 for i in t: s1=s s=s.replace(i+i,'') if s1!=s: t=list(set(s)) count+=1 if s=='': return 'Empty String' else: return s
nisevi I think you could improve your algorithm by not making it O(n^2), here is mine, maybe it helps.
python #!/bin/python import sys def super_reduced_string(s): # Complete this function i = 0 while len(s) > 0: if i == len(s)-1: return s else: if s[i] == s[i+1]: s = s[:i] + s[i+2:] i = 0 else: i +=1 return "Empty String" s = raw_input().strip() result = super_reduced_string(s) print(result)
Ashi_J [deleted]
shivammutreja25 Hi mate!
I had a similar approach, just that, I used LS.remove(LS[i]) instead of del LS[i] and it doesn't pass all the test cases.
How is it different?
rfeng2 when you remove, it is removing all the items in LS that have the same value as LS[i]
for example LS =[1,2,3,2,3,2], LS.remove(2) will remove all '2'
shivammutreja25 Hi
I think LS.remove(2) would remove the first 2 from the list.
_sh12 i = max(i-1, 0) will work, you dont have to do i=0 everytime you del elements.
_sh12 [deleted]martinberoiz even simpler:
def super_reduced_string(s): r = [] for c in s: last = r.pop() if r else "" if c != last: r.extend([last, c]) return "".join(r) or "Empty String"
parim_maheshwari please explain ur code
srisha_balaji127 Why do we have the delete operation twice?
tanmaysankhe del opertaion takes only one parameter
#reason for two del[] a = [a,b,c,d,e] del[1] a = [a,c,d,e] del[1] a = [a,d,e]
mihaig88 Nice and simple code I missed the part with break and mine didn't work
senrak Mine in C++ :
#include <bits/stdc++.h> using namespace std; int main() { string s; cin >> s; for(int i=0;i<(((int)s.length())-1);i++) { if(s[i]==s[i+1]){ s.erase(i,2); i=-1; } } cout<<(s.length()?s:"Empty String"); return 0; }
tusharchopade27 thanks!!!you r the only one who prefer c++!!
AimAmit [deleted]Nidhi99 Why is it an error when you don't typecast s.length() in the condition part of the loop?
mitchmcdee Simply python3 solution:
s = str(input()) i = 0 while i < len(s)-1: if s[i]==s[i+1]: s = s[:i] + s[i+2:] i = 0 else: i += 1 print(s if s else 'Empty String')
im_mohsin Can you pls explain this line?
print(s if s else 'Empty String')
mitchmcdee will print the reduced string (s) if there is one, else if s is empty it will print 'Empty String' as per spec :)
jessedgb Excellent answer~ I fell back on regex to solve this. I like how you reset i =0 whenever you perform a string slice rather than going through the whole string and then reseting.
RodneyShag Java solution - passes 100% of test cases
From my HackerRank solutions.
Use a Stack so that we can solve this problem by traversing the String just once!
Runtime: O(n)
Space Complexity: O(n)import java.util.Scanner; import java.util.Stack; public class Solution { public static void main(String[] args) { /* Read and save input */ Scanner scan = new Scanner(System.in); String str = scan.next(); scan.close(); /* Iterate through String, creating final result in a Stack */ Stack<Character> stack = new Stack<>(); for (int i = 0; i < str.length(); i++) { Character ch = str.charAt(i); if (!stack.isEmpty() && ch == stack.peek()) { stack.pop(); } else { stack.push(ch); } } /* Print final result */ if (stack.isEmpty()) { System.out.println("Empty String"); } else { for (char ch : stack) { System.out.print(ch); } } } }
Let me know if you have any questions.
VTU4997 what is the purpose of using this line " Stack stack = new Stack<>();"
RodneyShag That just creates a new stack variable called stack.
QuomoZ Haskell
import Data.Bool fix = until =<< ((==) =<<) deletePairs (x:xs:xss) | x == xs = deletePairs xss | otherwise = x : deletePairs (xs:xss) deletePairs xs = xs main = interact $ (bool id (const "Empty String") =<< null) . fix deletePairs
Abusing the cryptic function monad.
WhiteWolf_HT My solution in python
def super_reduced_string(s): # Complete this function ns2=[] for i in s: if len(ns2)==0: ns2.append(i) elif ns2[-1]==i: ns2.pop() else: ns2.append(i) if len(ns2)==0: return "Empty String" return ''.join(ns2)
Sort 808 Discussions, By:
Please Login in order to post a comment