Generate the nth Run-Count Sequence Term
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
A sequence of digit strings begins with `"1"`. Construct each later term by describing the consecutive runs in the preceding term:
- Split the preceding string into maximal runs of identical digits, keeping their left-to-right order.
- For each run, write its length in decimal, immediately followed by the digit in that run.
- Join those descriptions to form the next term.
For instance, applying this transformation to `"444116"` produces `"342116"`: three `4`s, two `1`s, and one `6`.
Given the positive integer `term`, return that numbered sequence element as a string. Numbering starts at `1`, so the first element is `"1"`.
### Examples
**Example 1**
```text
Input: term = 5
Output: "111221"
```
The fourth element is `"1211"`. Its runs describe one `1`, one `2`, and two `1`s, producing the fifth element.
**Example 2**
```text
Input: term = 6
Output: "312211"
```
The fifth element, `"111221"`, has three `1`s, two `2`s, and one `1`.
### Constraints
- `1 <= term <= 30`
### Optional Follow-up
Can you generate the requested term with an iterative implementation?
Overview: Generate the requested digit-string sequence term by describing maximal runs in each preceding term, with an optional iterative follow-up.
Community answers
Answer by Coderka14
#include
using namespace std;
class Solution
{
private:
string generateNext(const string& current)
{
string next;
int n = current.size();
for (int i = 0; i < n; )
{
int j = i;
while (j < n && current[j] == current[i])
{
j++;
}
int count = j - i;
next += to_string(count);
next += current[i];
i = j;
}
return next;
}
public:
string solution(int term)
{
string current = "1";
for (int i = 2; i <= term; i++)
{
current = generateNext(current);
}
return current;
}
};
/*
Approach: Iterative Run-Length Encoding
Initialize current = "1".
Generate terms 2 through term iteratively.
For each term, identify maximal runs of identical digits.
Append each run's length followed by its digit.
Replace current with the newly generated string.
Return current after generating the requested term.
Time Complexity:
O(L1 + L2 + ... + Lt), where Li is the length of term i.
Auxiliary Space:
O(Lt) for the current and next strings, asymptotically.
*/