Problem Statement
One of the challenges after marriage is traveling to have a great honeymoon. An inseparable part of such travel is hiking in the mountains.
When you shout in the mountains, you can sometimes hear an echo. The echo will say the same thing but it will make it sound longer.
In this problem, we will assume that the echo will repeat the i-th letter of your word i times. (Here we number the letters starting from 1 for the leftmost letter.)
For example, if you say "salam", the echo will say "saalllaaaammmmm".
The fortunate groom has just heard an echo. You are given the sound he heard as a string S of lowercase English letters. It is guaranteed that S was produced from the original word in the way described above. Please determine and return the original word that was said.
Definition
- Class:
- MarriageAndTravelingChallenge
- Method:
- solve
- Parameters:
- String
- Returns:
- String
- Method signature:
- String solve(String S)
- (be sure your method is public)
Constraints
- S will contain between 1 and 100 characters, inclusive.
- Each character in S will be a lowercase English letter.
- It's guaranteed that S can be produced from some string P by repeating the i-th character of P exactly i times, for each i.
Examples
"saalllaaaammmmm"
Returns: "salam"
The example from the problem statement.
"shhaaahhhhdddddaaaaaammmmmmmaaaaaaaaddddddddd"
Returns: "shahdamad"
"z"
Returns: "z"
"aaa"
Returns: "aa"
The original string was "aa". The first 'a' is repeated once and then the second 'a' is repeated twice.
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
Returns: "aaaaaaaaaaaaa"
"aeerrrttttyyyyyhhhhhhjjjjjjjnnnnnnnnbbbbbbbbbhhhhhhhhhhgggggggggggyyyyyyyyyyyyuuuuuuuuuuuuu"
Returns: "aertyhjnbhgyu"
"qwweeerrrrtttttyyyyyyqqqqqqqwwwwwwwweeeeeeeeerrrrrrrrrrttttttttttteeeeeeeeeeeeeeeeeeeeeeeee"
Returns: "qwertyqwertee"
"yzzyyy"
Returns: "yzy"
"zyyzzzyyyyyyyyy"
Returns: "zyzyy"
"eaaeeebbbbeeeeeffffffeeeeeee"
Returns: "eaebefe"
"aaaaaa"
Returns: "aaa"
"saalll"
Returns: "sal"