Home > other >  Remove All Adjacent Duplicates In String in C : Why is my iterator not entering into the for loop a
Remove All Adjacent Duplicates In String in C : Why is my iterator not entering into the for loop a

Time:08-24

image

CodePudding user response:

  • Your loop boundary, i < s.length(), is wrong since it'll let s[i 1] access the string out of bounds*.
  • You need to reset i when a match is found, which you do, but it's followed by i directly, so it will never find a match at s[0] == s[1] again.

Fixed:

string removeDuplicates(string s) {
    for (unsigned i = 0; i   1 < s.length();) { // corrected loop bounds
        if (s[i] == s[i   1]) {
            s.erase(i, 2);
            i = 0;
        } else   i;                            // only add 1 if no match is found
    }
    return s;
}

* The out of bounds access will really access the terminating \0 (since C 11, undefined behavior before that), but it's unnecessary since you can't erase it anyway.


A somewhat quicker version would be to not reset i to 0, but to continue searching at the current position:

string removeDuplicates(string s) {
    for (size_t i = s.length(); i-- > 1;) {
        if (s[i-1] == s[i]) {
            s.erase(i-1, 2);
              i;
        }
    }
    return s;
}

CodePudding user response:

The main problem of this for loop

for (int i = 0; i<s.length(); i  ) {
    if(s[i] == s[i 1]){
        s.erase(i,2);
        i=0;
    }
    
}

is that after erasing two adjacent elements the variable i is set to 0 and then at once is incremented in the for statement. So in the next iteration of the loop the variable i is equal to 1.

Consider the following string

"abba'

after erasing "bb" the string becomes equal to "aa" but after that the variable i is equal to 1 and in the next iteration of the loop you are comparing s[1] and s[2] that are 'a' and '\0'.

Rewrite the loop at least the following way

for ( std::string::size_type i = 0; i < s.length(); ) 
{
    if ( s[i] == s[i 1] )
    {
        s.erase(i,2);
        i=0;
    }
    else
    {
          i;
    }
}
  • Related