Loading...

Sort 707 Discussions, By:

  • tao_zhang + 31 comments

    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);
            }
        }
    }
    
    • SK
      Stef2k15 + 10 comments

      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 + 3 comments

        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.

        • SK
          Stef2k15 + 1 comment

          Ok. Thanks for your answer! I'll keep that in mind next time.

          • shraddhashrivas1 + 0 comments

            Thanks for pointing out about the locking /unlocking thing. :)

        • ujjawaljaiswal21 + 0 comments

          Thank you for the advice on unlocking and locking.

        • ranjithkumar2811 + 0 comments

          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

      • NM
        nm1511 + 2 comments

        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 + 2 comments

          I used recursion but doing i=0 is so elegant and clean.

          • krish258 + 0 comments

            true, it just makes the solution so readable.

          • tadavartisujith + 2 comments

            How did you do using recursion ?

            • M
              Monkeyanator + 0 comments

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

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

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

            goodluck_deciphering, #if_it_was_difficult_for_me_i_make_it_difficult_for_everyone, #look_how_smart_i_am

      • JY
        jyiyao + 0 comments

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

      • AR
        Ankur_Beginning + 1 comment

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

        • T
          Tutankhamun + 0 comments

          it's i-1 up to (but not including) i+1. So i-1 and i are deleted

      • aldoinfanzon + 0 comments

        This solution is very nice and clean good work

      • VP
        vnspriyanka476 + 2 comments

        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.

        • AH
          Ausaf + 0 comments
          [deleted]
        • ishabandi + 1 comment

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

            thanks

      • jagacode + 4 comments

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

        • ishabandi + 0 comments

          https://www.hackerrank.com/challenges/reduced-string/forum/comments/152973

          See, this one.

        • NE
          neelkusum93 + 0 comments

          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!

        • LN
          BALYAM_muralidh2 + 0 comments
          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);
              }
          
        • LN
          BALYAM_muralidh2 + 0 comments

          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 )

      • DP
        divs4debu + 1 comment
        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?

        • IC
          winty95 + 0 comments

          In my solution result.delete(i-1, i+1); i-=2; if(i<0) i=0; Our performence might be better just i=0.

      • MV
        maheshvangala191 + 0 comments

        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

      • GY
        gokulYadav + 0 comments

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

    • AM
      abhishek1810 + 4 comments

      Why you are making i=0; even though it works if you dont make i=0.

      Thanks in advance..

      • SK
        Stef2k15 + 1 comment

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

          try this way: C++14

          string super_reduced_string(string s)
          {
             for(unsigned int i=1; i<s.length(); ++i)
                if(s.at(i-1)==s.at(i))
                {
                   s.erase(i-1,2);
                   i=0;
                }
             if(s.length()==0)
                return "Empty String";
             else
                return s;
          }
          
      • N
        Kanna_19 + 0 comments
        [deleted]
      • alvin_ega93 + 2 comments

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

          not necessary.. if u bring pointer (say i) to a previous value after deleting

        • kdishashetty2992 + 0 comments

          This comment helped me actually understand why i=0;

      • NE
        neelkusum93 + 1 comment

        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.

        • DP
          divs4debu + 2 comments
          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

          • AC
            abhi_chawla96 + 0 comments

            what is the use of if(i-1>0) i=i-2 ??

          • AJ
            mca_amit89 + 0 comments

            i am trying solve this code but I did not please clarify why delete used and its not support which version is working.

    • wkusnierczyk + 1 comment

      You might want to research a bit on the complexity of joining strings in java, and how it scales. (It doesn't.)

      • tao_zhang + 1 comment

        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.

        • GH
          GokayH + 2 comments

          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

          • VM
            vmalakhin + 0 comments

            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));
                }
            
          • AM
            ajeet_meena + 2 comments

            We can use linked list for o(n) time complexiety. Guide me if I am wrong.

            • VM
              vmalakhin + 1 comment

              could work but stack makes more sense especially if it's array based.

              • AM
                ajeet_meena + 2 comments

                Exactly, Stack is the answer. I wonder why people here are managing strings or writing regex.

                • VM
                  vmalakhin + 0 comments

                  that's really good question.

                • silja_tirronen + 9 comments

                  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);
                      }
                  
                  • AH
                    sleepyhollow + 0 comments
                    [deleted]
                  • AH
                    sleepyhollow + 0 comments
                    [deleted]
                  • AH
                    sleepyhollow + 0 comments

                    This is a really good solution. Some languages do not allow modifying the iterable while looping on it. Awesome!

                  • AJ
                    atishayjain708 + 0 comments

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

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

                      Thank you kaustav

                  • YK
                    yklyuyev + 3 comments

                    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?

                    • MJ
                      jaco0797 + 1 comment

                      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?

                      • BK
                        _TheFlyingOtter + 1 comment

                        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.

                        • KK
                          kukanishka + 1 comment

                          why can't it be only if res[len(res)-1] == c

                          • LK
                            liam_kirsh + 0 comments

                            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.

                    • KK
                      kukanishka + 0 comments

                      why can't it be only if res[len(res)-1] == c??

                    • LK
                      liam_kirsh + 0 comments

                      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"
                      
                  • TM
                    tim_mathias + 0 comments

                    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";
                    }
                    
                  • ST
                    satummal + 0 comments

                    Neat...

                  • S
                    srinidhi_343 + 1 comment

                    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.

                    • TD
                      taciosd + 0 comments

                      Actually, abcdb is correct. The two b letters left in the string are not next to each other, so this is the final reduced form of the original string.

            • C
              gps_gaurav + 0 comments

              u can use array for O(n) complexiety.

    • Shady_Shah + 1 comment

      What does i=0 do here exactly?

      • C
        VARIK + 0 comments

        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 + 2 comments

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

        i = -1 is sufficient

      • VK
        vasukapil2196 + 1 comment

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

        • S“
          pnenad38 + 0 comments

          int i; if(i == 0) i = -1; else i = i - 2;

    • karadeniz + 0 comments

      Any reason using SubString over Remove? Is there a big performance difference between those?

    • SR
      sharan281 + 0 comments

      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)

    • LA
      lucas2213690 + 0 comments

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

      Thank you

    • MV
      manikesh_verma + 0 comments

      This is not correct.. it removed b as well

    • AK
      K1408442 + 0 comments
      [deleted]
    • saif01md + 3 comments

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

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

      • SM
        smudassir719 + 0 comments

        initialize i = 1 in for loop

      • Hacker_RK + 0 comments

        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.

    • IS
      ishansrivastava1 + 0 comments

      one doubt can u plz clear it ,there is nowhere mentioned to remove duplicate letters so why r u removing duplicate ones

    • Tommy_Tran + 1 comment

      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?

      • AH
        Ausaf + 0 comments

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

    • tugrulcebe + 0 comments

      Mine in Perl

      use strict;

      my @newArray; my $string = ;

      my @str = split //, count = 0;

      for(my i if(i] eq i+1]) {
      splice @str, i = -1;
      }
      } my lf == 0) { print "Empty String"; } else { print @str; }

    • AnonymousNovice + 0 comments

      Thank You for teaching something valuable.

    • jagacode + 1 comment

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

      • RP
        raghav_prakash + 0 comments

        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)

    • RP
      raghav_prakash + 0 comments

      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!

    • ray_sid + 1 comment

      why did you do i=0 in the end

      • Hacker_RK + 0 comments

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

    • RC
      RickyCaoCao + 0 comments

      Good solution but I think using StringBuilder will save us from a lot of String Object creations.

    • AS
      avanii247 + 2 comments

      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 + 1 comment
        use for(int i=0;i<(s.length());i++)
        
        • AS
          avanii247 + 0 comments

          My if statement if(s.charAt(i)==s.charAt(i+1)) will throw an out of bound exception

      • PM
        pd121193 + 0 comments

        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.

    • IB
      twitu + 0 comments

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

    • RB
      rbborneo + 0 comments

      This seems little inefficient going back to index 0 everytime you delete something?

    • [DELETED] + 0 comments
      [deleted]
    • AK
      pep1439 + 0 comments

      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);
              }
          }
      
    • PS
      purvashah98 + 0 comments

      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!

    • SB
      sankalp29 + 0 comments

      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?

    • VB
      tecnocratay + 0 comments

      great solution

    • PD
      dixitpranshu99 + 0 comments

      Please explain why do you write "i=0" in the if condition.

    • YB
      balgabekov1 + 0 comments
      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'
      
    • SA
      Shobith_ak + 0 comments

      could u please explain why i=0? I did not get that point

  • DasShubhadeep + 8 comments

    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;
    }
    
    • AB
      Yoam13 + 1 comment

      Please Explain Your Code...

      • DasShubhadeep + 0 comments

        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.

    • merwinmicku + 1 comment

      well done bro .....it made me think differently..and being a C user i was getting a hell of time....

      • DasShubhadeep + 0 comments

        Thanks.

    • positivedeist_07 + 1 comment

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

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

          Yeah sure, time complexity will increase in that case. Btw, elegant coding and interesting thinking on ur solution :)

    • Hemanth_jain + 1 comment

      please explain ur code!

      • DasShubhadeep + 0 comments

        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.

    • rob_in_1 + 1 comment

      what's the value of stack[-1] ?

      • CiPHeR33 + 0 comments

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

    • ProgramForFuture + 0 comments

      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';
      }
      
    • JL
      jluisg_23 + 0 comments

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

      This is an elegant solution =)

  • AA
    kodomass + 11 comments
    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;
    
    • SJ
      sridharjajoo + 0 comments

      thnx!..it really helped

    • KJ
      kishore95cod + 0 comments

      thanks a lot bro

    • SD
      sdaqiq0 + 0 comments

      I was half way through doing this but got lost some where in the middle :(

    • VT
      vtovmasyan + 1 comment
      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());
      }
      
      • R
        f2014411 + 0 comments

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

    • SS
      suhail545 + 1 comment

      what is static_cast

      • fstanley + 0 comments

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

    • RK
      karajrish + 1 comment

      while(i < static_cast< int > (str.size()-1))

      Can someone explain me what does this line do?

      • fstanley + 3 comments

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

          Isn't it better to use str.length() ?

          • KK
            krishnakeshav + 1 comment

            Nope, since both will have diffferent functionalities in this case.length() will only return for initial string whereas size keeps changing.

            • fstanley + 1 comment

              Sorry, this is wrong. STL string size() and length() are synonyms. They will always return the same value.

              • KK
                krishnakeshav + 0 comments

                aah..yes...apparently both of them shows same behaviour. I was missing static cast on length()

        • AG
          nkit1997knw + 0 comments

          Can't we use just (int) instead of static_cast

        • AI
          abyl_ikhsanov + 1 comment

          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.

          • CS
            Crystal_star + 0 comments

            can't we use "unsigned int i" instead.?

    • bhavya_it16 + 0 comments
      [deleted]
    • IR
      isanrivkin + 0 comments
      [deleted]
    • juaxix + 1 comment

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

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

    • kavyasree42 + 0 comments

      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

    • SM
      shulomithii26 + 0 comments

      why i++ again ?

  • CH
    craig_holland + 2 comments

    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'
    
    • TA
      ThundercloudABM + 0 comments

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

      I am confused on

      re.compile(r'(\w)(\1)')
      

      Would you mind provide some info or comments?

      • TA
        ThundercloudABM + 0 comments

        \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'.
  • VK
    inxcess + 7 comments

    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)
    
    • CJ
      charzard + 2 comments

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

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

      • amolkavitkar_19 + 1 comment

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

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

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

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

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

        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'

        • SM
          shivammutreja25 + 0 comments

          Hi

          I think LS.remove(2) would remove the first 2 from the list.

    • _sh12 + 0 comments

      i = max(i-1, 0) will work, you dont have to do i=0 everytime you del elements.

    • _sh12 + 0 comments
      [deleted]
    • MB
      martinberoiz + 1 comment

      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"
      
      • PM
        parim_maheshwari + 0 comments

        please explain ur code

    • SB
      srisha_balaji127 + 1 comment

      Why do we have the delete operation twice?

      • TS
        tanmaysankhe97 + 0 comments

        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]
        
    • MG
      mihaig88 + 0 comments

      Nice and simple code I missed the part with break and mine didn't work

  • QuomoZ + 0 comments

    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.

  • RR
    senrak + 3 comments

    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;
    }
    
    • TC
      tusharchopade27 + 0 comments

      thanks!!!you r the only one who prefer c++!!

    • PN
      png9981 + 1 comment

      Can you explain for me why there is i=-1 ?

      • RR
        senrak + 1 comment

        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.

        • PN
          png9981 + 0 comments

          Thanks for the help.

    • AK
      contacttoamit00 + 0 comments
      [deleted]
  • mitchmcdee + 2 comments

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

      Can you pls explain this line?

      print(s if s else 'Empty String')

      • mitchmcdee + 0 comments

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

    • jessedgb + 0 comments

      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.

  • rshaghoulian + 1 comment

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

      what is the purpose of using this line " Stack stack = new Stack<>();"

      • rshaghoulian + 0 comments

        That just creates a new stack variable called stack.

        HackerRank solutions.

  • MB
    tawriffic + 0 comments

    Javascript solution:

    var arr = readLine().split('');
        for (var i = 0; i < arr.length; i++) {
            if (arr[i] === arr[i + 1]) {
                arr.splice(i, 2);
                i = -1;
            }
        }
        if (arr.length === 0) {
            console.log('Empty String');
        } else {
        console.log(arr.join(''));
        }