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.

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.

if i!=0, making i=i-1 will be efficient.

will you pls explain why you are deleting i-1 and i+1 element

This solution is very nice and clean good work

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.

i cant understand why that i=0 is used for ...can u explain me?

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?

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

i too implemented the same but stuck in loop thanks for zero

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.

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.

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.

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.

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.

i = -1 is sufficient

can you explain how i = (i==0) ? -1 : i-2; works?

maybe try s.length()-1 ? looks like charAt(i+1) would be out of range

initialize i = 1 in for loop

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.

it should return abcad as u have to remove only adjacent pair of letters if they r same

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)

so that the loop starts from the beggning at the end of every pass....

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.

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.

Thanks.

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.

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.

Nothing, he's initializing the stack with -1 as its index.

Why are we using i > -1 and i--? Can we not simply do it without using it?

converts unsigned int (str.size()) to int for comparison to (i).

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.

too long, feels like the obfuscated Python Hello World except it's not obfuscated

\1 is a regex backreference.

The backreference placeholder \1 is substituted with the substring that matches the group 1 pattern (\2 is 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 pattern r'(\w)(\1)':

• Group 1 contains (\w), which matches 'a', so \1 now 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 \1 becomes a 'b'; since the next character in the string is also a 'b' the regex is satisfied, it stops searching, and returns 'bb'.

fyi: I had a very similiar approach (basically the same) and didn't have a time issue

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)

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'

please explain ur code

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]

because when you erase some part of string, the length changes. and we need to start from beginning of string, hence we require i=-1, which will become i=0 after updation in the for loop.

will print the reduced string (s) if there is one, else if s is empty it will print 'Empty String' as per spec :)

That just creates a new stack variable called stack.

HackerRank solutions.