Last Updated: 28 May, 2025

Keyboard Problem

Moderate

Asked in company

Solve now

Problem statement

Alex is having a problem with his keyboard. If he presses any key, he may get extra occurrences of that character. Example: If he wants to write "hey", he may end up typing: hhey, hheey, heey, hhheyyy, etc.

You are given a string 'S' typed by Alex. Your task is to find out the number of possible strings Alex was trying to type and return the same.

Output can be very large. Return (number of ways % 1e9 + 7). Where % is the modular operator.

For Example :

Let 'S' = "adddef".
Alex could have been trying to type:
- "adef" (second and third 'd' are extra)
- "addef" (second 'd' is extra)
- "addef" (third 'd' is extra)
- "adddef" (no extra characters) 
So we have 3 distinct possibilities: "adef", "addef", and "adddef".
Therefore, the answer is 3.

Input Format :

The first line contains a string 'S'.

Output Format :

Return the number of possible original strings modulo 1e9 + 7.

Note :

You don't need to print anything. Just implement the given function.

Constraints :

1 <= |S| <= 10^5
'S' contains only lowercase English letters
Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach:

Group consecutive identical characters together.
For each group of size 'C', Alex could have intended 1, 2, 3, ..., or 'C' characters of that type.
The total number of ways is the product of possibilities for each group.

Algorithm:

Initialize variable 'MOD' to 1000000007.
Initialize variable 'N' as length of string 'S'.
Initialize variable 'result' to 1.
Initialize variable 'i' to 0.
While 'i' < 'N':
- Initialize variable 'count' to 1.
- Initialize variable 'j' to 'i + 1'.
- While 'j' < 'N' and 'S[j]' == 'S[i]':
  - Increment 'count' by 1.
  - Increment 'j' by 1.
- Multiply 'result' by 'count' and take modulo 'MOD'.
- Set 'i' to 'j'.
Return 'result'.

Solve now