3330. Find the Original Typed String I

EasyString

Problem Description

Alice is trying to type a specific string on her computer. However, she sometimes presses a key for too long, causing a character to be typed multiple times. Despite her efforts to type correctly, Alice acknowledges that this mistake may occur at most once in her typing. You are provided with a string word, depicting the final output shown on Alice's screen. Your task is to determine the total number of possible original strings Alice might have intended to type.

Intuition

The core idea behind solving this problem is to recognize the scenarios where Alice's clumsy typing might have resulted in a character being repeated. Given that such an occurrence can happen at most once, examining each pair of adjacent characters helps us detect where a repetition might have occurred. By doing this, we can count the number of potential original strings Alice may have intended, which corresponds to counting each pair of identical consecutive characters. The solution exploits the fact that any such repetition indicates a possibility of an original string. Thus, the solution essentially involves iterating through the string, comparing each pair of consecutive characters, and counting these potential slip-ups to arrive at the total count of possible original strings.

Solution Approach

The solution to the problem is implemented by iterating through the string word to assess any potential instances where Alice might have pressed a key for too long. The algorithm involves the following steps:

Initialization: Begin by assuming that the number of possible original strings is at least 1. This accounts for the scenario where Alice may have typed the word without any errors.
Pairwise Comparison: Use a function like pairwise to compare each consecutive pair of characters in the string word.
Count Repetitions: For each pair of consecutive characters (x, y), check if x is equal to y. If they are equal, it implies a repetition has occurred, indicating a potential original string.
Calculate Total: Sum the number of such repetitions identified during iteration. The total number of different possible original strings is given by 1 + the sum of such identical consecutive pairs.

Here's the implementation encapsulated in a method:

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

This approach efficiently counts the potential original strings by focusing on detecting and acknowledging each feasible typo occurrence within the constraints of the problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with an example. Suppose Alice has typed the string word = "aallee".

Initialization: We start by assuming that there's at least 1 possible original string. This initial value assumes there are no errors in typing.
Pairwise Comparison: We'll compare each pair of consecutive characters in the string.
- Compare 'a' and 'a': They are equal, indicating a possible original string if Alice intended to type just one 'a'.
- Compare 'a' and 'l': They are different, suggesting no error here.
- Compare 'l' and 'l': They are equal, indicating another potential original string if Alice meant to type a single 'l'.
- Compare 'l' and 'e': They are different, implying no error.
- Compare 'e' and 'e': They are equal, indicating one more potential original string if Alice intended one 'e'.
Count Repetitions: In this case, we found three pairs ('aa', 'll', and 'ee') where the consecutive characters were the same. Each such pair suggests a potential error at that position.
Calculate Total: The total number of different possible original strings is 1 (initial assumption) + number of repetitions (3), resulting in a total of 4 possible original strings that Alice might have intended: "alee", "alle", or "alee".

The implemented method would return this count:

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

Solution Implementation

1from itertools import tee
2
3class Solution:
4    def possibleStringCount(self, word: str) -> int:
5        """
6        Counts the possible strings where two consecutive characters are the same.
7      
8        :param word: A string in which to count consecutive identical character pairs.
9        :return: The count of possible strings including pairs with consecutive identical characters.
10        """
11      
12        # Function to yield pairs of consecutive elements from the input iterable
13        def pairwise(iterable):
14            a, b = tee(iterable)
15            next(b, None)
16            return zip(a, b)
17
18        # Start with an initial count of 1 (possibly considering the original string as a valid case)
19        # Sum the number of times consecutive characters (x and y) in the word are equal
20        return 1 + sum(x == y for x, y in pairwise(word))
21

1class Solution {
2    public int possibleStringCount(String word) {
3        int count = 1; // Initialize the count to 1 because the first character is always counted
4        // Loop through the string starting from the second character
5        for (int i = 1; i < word.length(); ++i) {
6            // Check if the current character is the same as the previous one
7            if (word.charAt(i) == word.charAt(i - 1)) {
8                ++count; // Increment the count if characters are the same
9            }
10        }
11        return count; // Return the total count of adjacent duplicate characters
12    }
13}
14

1#include <string>
2
3class Solution {
4public:
5    int possibleStringCount(std::string word) {
6        // Initialize a frequency counter for contiguous characters
7        int frequency = 1; 
8      
9        // Loop through the string starting from the second character
10        for (int i = 1; i < word.size(); ++i) {
11            // Increment the frequency counter if the current character matches the previous one
12            frequency += (word[i] == word[i - 1]);
13        }
14      
15        // Return the final frequency count
16        return frequency;
17    }
18};
19

1// Function to count the number of consecutive repeating characters in a string
2function possibleStringCount(word: string): number {
3    let count = 1; // Initialize count to 1 to account for the first character
4
5    // Loop through the string starting from the second character
6    for (let i = 1; i < word.length; ++i) {
7        // If the current character is the same as the previous one, increment count
8        if (word[i] === word[i - 1]) {
9            count++;
10        }
11    }
12
13    return count; // Return the total count of consecutive repeating characters
14}
15

Time and Space Complexity

The function possibleStringCount iterates over the input word to count consecutive pairs of equal characters. Since the function utilizes pairwise to create pairs from the string, the time complexity is O(n), where n is the length of word. This is because the iteration over the string is linear.

For space complexity, the code primarily uses an iterator for pairwise, making the space complexity O(1) as it doesn't require additional space proportional to the input size.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don’t know