Skip to content

3330. Find the Original Typed String I

Description

Alice is attempting to type a specific string on her computer. However, she tends to be clumsy and may press a key for too long, resulting in a character being typed multiple times.

Although Alice tried to focus on her typing, she is aware that she may still have done this at most once.

You are given a string word, which represents the final output displayed on Alice's screen.

Return the total number of possible original strings that Alice might have intended to type.

 

Example 1:

Input: word = "abbcccc"

Output: 5

Explanation:

The possible strings are: "abbcccc", "abbccc", "abbcc", "abbc", and "abcccc".

Example 2:

Input: word = "abcd"

Output: 1

Explanation:

The only possible string is "abcd".

Example 3:

Input: word = "aaaa"

Output: 4

 

Constraints:

  • 1 <= word.length <= 100
  • word consists only of lowercase English letters.

Solutions

Solution 1: Direct Traversal

According to the problem description, if all adjacent characters are different, there is only 1 possible original input string. If there is 1 pair of adjacent identical characters, such as "abbc", then there are 2 possible original strings: "abc" and "abbc".

By analogy, if there are \(k\) pairs of adjacent identical characters, then there are \(k + 1\) possible original input strings.

Therefore, we just need to traverse the string, count the number of pairs of adjacent identical characters, and add 1.

The time complexity is \(O(n)\), where \(n\) is the length of the string. The space complexity is \(O(1)\).

1
2
3
class Solution:
    def possibleStringCount(self, word: str) -> int:
        return 1 + sum(x == y for x, y in pairwise(word))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int possibleStringCount(String word) {
        int f = 1;
        for (int i = 1; i < word.length(); ++i) {
            if (word.charAt(i) == word.charAt(i - 1)) {
                ++f;
            }
        }
        return f;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    int possibleStringCount(string word) {
        int f = 1;
        for (int i = 1; i < word.size(); ++i) {
            f += word[i] == word[i - 1];
        }
        return f;
    }
};

1
2
3
4
5
6
7
8
9
func possibleStringCount(word string) int {
    f := 1
    for i := 1; i < len(word); i++ {
        if word[i] == word[i-1] {
            f++
        }
    }
    return f
}

1
2
3
4
5
6
7
function possibleStringCount(word: string): number {
    let f = 1;
    for (let i = 1; i < word.length; ++i) {
        f += word[i] === word[i - 1] ? 1 : 0;
    }
    return f;
}

1
2
3
4
5
impl Solution {
    pub fn possible_string_count(word: String) -> i32 {
        1 + word.as_bytes().windows(2).filter(|w| w[0] == w[1]).count() as i32
    }
}

Comments