Connection Status:
Competition Arena > StringCmp

StringCmp

SRM 124 · 2002-12-12 · by dgoodman

SRM 124 · 2002-12-12 · by dgoodman
Class Name: StringCmp
Return Type: int
Method Name: firstDif
Arg Types: (string, string)
Problem Statement

Problem Statement

We can try to compress the representation of a string of letters with a Run Length Encoding. This encoding represents a repeated character with a digit sequence giving the number of repetitions followed by the character. For example, "xb32c5d" represents a string which has 39 characters ("xbccc...cddddd"). A letter that is not immediately preceded by a digit sequence represents just that single character.

We want to be able to compare two Run Length Encodings to see if they represent the same string. Create a class StringCmp that contains the method firstDif that takes two encodings as inputs and returns the first index where the represented strings differ. If the represented strings are identical, return -1.

Notes

  • "34ab", "1a0x033ab" and "a33ab" all represent the same String
  • return a 0-based index (if they differ in the first position, return 0)
  • if the strings match up to the point where one string continues but the other ends, return the length of the shorter one

Constraints

  • code1 contains between 1 and 50 characters inclusive
  • code2 contains between 1 and 50 characters inclusive
  • code1 and code2 contain only digits and lowercase letters 'a'-'z'
  • the last character in code1 is a letter
  • the last character in code2 is a letter
  • neither code1 nor code2 contains a sequence of more than 8 consecutive digits
Examples
0)
"98765432aa"
"98765433a"
Returns: -1

The two represented strings are identical. Each has length = 98,765,433.

1)
"0c"
"00d"
Returns: -1

The two represented strings are both empty strings

2)
"543e"
"0f"
Returns: 0

The empty string is shorter. Its length is 0.

3)
"0a0b00c"
"a2b0x2b1c"
Returns: 0
4)
"13a10bc"
"3a5aa3a1a2b0c2b3c"
Returns: 17
5)
"a3bc"
"ab04c"
Returns: 2

The two represented strings are "abbbc" and "abcccc"

Submissions are judged against all 36 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class StringCmp with a public method int firstDif(string code1, string code2) · 36 test cases · 2 s / 256 MB per case

Submitting as anonymous