 # KOL1505 - Editorial

Author: Praveen Dhinwa
Tester: Kevin Atienza
Editorialist: Kevin Atienza

### PREREQUISITES:

String processing

Cakewalk

### PROBLEM:

Given two strings, the following operation can be done in any string: given two consecutive, same, letters, remove one of them. Can we make the two strings equal?

### QUICK EXPLANATION:

Simply remove all consecutive duplicate letters in both strings (leaving just one for each consecutive sequence), and check if the resulting strings are equal.

### EXPLANATION:

The solution should be apparent: Simply remove all consecutive duplicate letters in both strings (leaving just one for each consecutive sequence), and check if the resulting strings are equal. This is correct because if we can turn both strings into a string having consecutive duplicate letters, then we can continue removing the duplicates until we are left with none, thus both strings can be turned into the same string but having no consecutive duplicate letters.

Here’s one way to perform it, in C:

``````void remove_duplicates(char *c) {
int i = 1;
for (int j = 1; c[j]; j++) {
if (c[j] != c[j-1]) c[i++] = c[j];
}
c[i] = 0;
}
``````

This performs the operation in-place, destroying the original string in the process.

There’s a nice way to do it in C++:

``````string remove_duplicates(string s) {
return string(s.begin(), unique(s.begin(), s.end()));
}
``````

It uses the `std::unique` function, which does exactly what we want!

Finally, in Java:

``````static String removeDuplicates(String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (i == 0 || s.charAt(i-1) != s.charAt(i)) sb.append(s.charAt(i));
}
return sb.toString();
}
``````

After implementing this function, simply call this on both input strings, and check if they are equal!

Gotcha: A possible mistake one can make when implementing string comparison is stopping the comparison prematurely. Consider the following C code: (It prints `Yes` if `a` and `b` are the same string, and `No` otherwise.)

``````bool good = true;
int a_len = strlen(a);
int b_len = strlen(b);
for (int i = 0; i < a_len && i < b_len; i++) {
if (a[i] != b[i]) {
good = false;
break;
}
}
puts(good ? "Yes" : "No");
``````

Can you point out what’s wrong with it?

The code above is wrong because it fails when `a` is a proper prefix of `b`, or vice versa. This is because `good` only becomes `false` when it finds two different characters in the same position from `a` and `b`, which isn’t the case when one is a prefix of the other. Here are a couple of ways to fix this:

• Check whether the lengths are equal first.
• Replace the loop condition by `i < a_len || i < b_len`,
• Better yet, just use builtin methods like `strcmp`.

Extra: There’s a Unix utility that does this. The `uniq` command, when fed some text input, outputs it, but with adjacent identical lines collapsed to one. This is usually coupled with the `sort` command to output all distinct lines in the input.

O(|s| + |t|)

### AUTHOR’S AND TESTER’S SOLUTIONS:

2 Likes

@kevinsogo:
Wow! std::unique function is really nice. This problem is meant for this STL function 2 Likes

This problem seems to be in the wrong section of the practice problems. It’ definitely not “medium”.

//