You are not logged in. Please login at www.codechef.com to post your questions!

×

KOL1505 - Editorial

PROBLEM LINK:

Contest
Practice

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|)$

AUTHOR'S AND TESTER'S SOLUTIONS:

setter
tester

This question is marked "community wiki".

asked 26 Dec '15, 06:26

kevinsogo's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

edited 13 Aug '17, 19:33

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53136170

This problem seems to be in the wrong section of the practice problems. It' definitely not "medium".

(18 Mar '16, 21:59) ceilks7★

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

link

answered 03 Jan '16, 19:13

shiva_google's gravatar image

2★shiva_google
974
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,639
×643
×113
×10

question asked: 26 Dec '15, 06:26

question was seen: 2,108 times

last updated: 13 Aug '17, 19:33