A packaging line uses an automated stamping arm to print serial codes onto shipping labels, one character at a time from left to right. On any given production run, the arm's return spring can jam at most a single time; when it jams, the arm strikes the very same character several extra times in a row before the spring frees itself and normal stamping resumes for the rest of the code. You are given the text that was actually printed on a shipped label. Determine how many distinct original codes the operator could have intended to stamp, assuming the jam either never happened during that run or happened exactly once.
A single line containing the string s — the text printed on the label, consisting only of lowercase English letters.
A single integer: the number of distinct original codes consistent with s under the at-most-one-jam rule described above.
s consists only of lowercase English letters ('a'-'z').Example 1
Input
abbcccc
Expected
5
Explanation
Runs are a(1), b(2), c(4). If the arm never jammed, the original is exactly 'abbcccc' (1 way). If the jam hit the b-run (length 2), the original b-count could only be 1, giving 'abcccc' (1 way). If the jam hit the c-run (length 4), the original c-count could be 1, 2, or 3, giving 'abbc', 'abbcc', 'abbccc' (3 ways). Total: 1 + 1 + 3 = 5.
Example 2
Input
aaaa
Expected
4
Explanation
There is a single run a(4). If no jam occurred, the original is 'aaaa' (1 way). If the jam hit this run, the original a-count could be 1, 2, or 3, giving 'a', 'aa', 'aaa' (3 ways). Total: 1 + 3 = 4.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →