Keyboard Problem

Moderate

0/80

0 upvote

Asked in company

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

aab

Sample Output 1 :

Explanation of sample input 1 :

Alex typed "aab". The possible original strings he intended are:
- "ab" (second 'a' is extra)
- "aab" (no characters are extra)
So we have 2 distinct possibilities: "ab" and "aab".
Thus, the answer is 2.

Sample Input 2 :

aaabbc

Sample Output 2 :

Hint 1

For each group of consecutive identical characters, Alex could have intended any number from 1 to the total count of that character.

Approaches (1)

Approach 1

Math

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'.

Time Complexity

O(N), where 'N' is the length of string 'S'.

We iterate through each character in the string once to group consecutive identical characters. Thus, the overall time complexity is of the order O(N).

Space Complexity

O(1).

We use only a constant amount of extra space for variables like 'count', 'result', and loop counters. Thus, the overall space complexity is of the order O(1).

(100% EXP penalty)

Keyboard Problem

Console