Decode and Count Unique Characters in Run-Length Encoded String

mediumSave

Hash TableSimulationString

You are given a string s that has been encoded using a simple run-length encoding scheme. The encoding works as follows: a number (representing a count) is followed by the character it repeats. For example, "3a2b1c" means "aaabbc". Note that the count can be a multi-digit number. Your task is to first decode the given run-length encoded string and then count the number of unique characters in the decoded string.

Example 1

Input

[
  "3a2b1c"
]

Output

Explanation. "3a2b1c" decodes to "aaabbc". The unique characters are 'a', 'b', 'c'. There are 3 unique characters.

Example 2

Input

[
  "1a1b1a"
]

Output

Explanation. "1a1b1a" decodes to "aba". The unique characters are 'a', 'b'. There are 2 unique characters.

Example 3

Input

[
  "10z1x"
]

Output

Explanation. "10z1x" decodes to "zzzzzzzzzzx". The unique characters are 'z', 'x'. There are 2 unique characters.

Example 4

Input

[
  "1a"
]

Output

Explanation. "1a" decodes to "a". The unique character is 'a'. There is 1 unique character.

Example 5

Input

[
  "1a1a1a"
]

Output

Explanation. "1a1a1a" decodes to "aaa". The unique character is 'a'. There is 1 unique character.

Example 6

Input

[
  "5b"
]

Output

Explanation. "5b" decodes to "bbbbb". The unique character is 'b'. There is 1 unique character.

Example 7

Input

[
  "2a3b4c1d2e"
]

Output

Explanation. "2a3b4c1d2e" decodes to "aabbbccdddee". The unique characters are 'a', 'b', 'c', 'd', 'e'. There are 5 unique characters.

Example 8

Input

[
  "1z2y3x10w"
]

Output

Explanation. "1z2y3x10w" decodes to "zyyyxxxwwwwwwwwww". The unique characters are 'z', 'y', 'x', 'w'. There are 4 unique characters.

Follow-up: What if the encoding also included an escape character to represent digits themselves? For example, 'a\23' means 'a' repeated 23 times, but 'a2' followed by 'b3' (using a hypothetical count-first scheme) would mean 'aa' followed by 'bbb'. How would you modify your parser to distinguish between a digit that is part of the count and a digit that is a character to be repeated if the character itself could be a digit?

Constraints:

1. The input string `s` will only contain lowercase English letters ('a'-'z') and digits ('0'-'9'). 2. The encoding will always be valid, meaning a digit will always be followed by a letter, and a letter will always be followed by a digit (or be the end of the string if it's the last character). An encoded segment will always start with a digit representing the count. 3. The count for any character will be at least 1. 4. The maximum length of the decoded string will not exceed 10000 characters. 5. The length of the input string `s` will be between 1 and 1000.

Views: 3