PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Kevin Atienza
Editorialist: Kevin Atienza
PREREQUISITES:
String processing
DIFFICULTY
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.
Time Complexity:
O(|s| + |t|)
