# Find the Original Typed String I
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-original-typed-string-i)
Canonical: https://scaleengineer.com/dsa/problems/find-the-original-typed-string-i
**Data structures:** String
**Companies:** [Lowe's](https://scaleengineer.com/companies/lowe's)
---
## Problem
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.

# Approaches
## Grouping and Counting
This approach breaks the problem into two distinct steps. First, it processes the input string to identify and store all groups of consecutive identical characters. For example, "abbcccc" would be represented as groups of ('a', 1), ('b', 2), and ('c', 4). In the second step, it calculates the number of possible original strings based on these stored groups.
**Time:** O(N), where N is the length of `word`. The first loop to create groups iterates through the string once. The second loop iterates through the groups, and the number of groups (K) is at most N. So, the total time is O(N + K) which simplifies to O(N). · **Space:** O(K), where K is the number of consecutive character groups. In the worst-case scenario (e.g., "abcdef"), K is equal to N (the length of the string), leading to O(N) space complexity.
**Pros:** The logic is very clear and easy to follow as it's separated into two distinct phases: grouping and counting.; The separation of concerns can make the code easier to debug and maintain.
**Cons:** Requires extra space to store the character groups, which can be proportional to the length of the string in the worst case.
### Explanation
The core idea is that a long press could have occurred on any character that appears consecutively more than once. The total number of possibilities is the sum of two scenarios:
1.  **No long press:** The original string is the same as the input `word`. This accounts for one possibility.
2.  **Exactly one long press:** A long press could have happened on any group of characters with a length greater than 1. For a group of length `k`, there are `k-1` shorter original versions. For example, if we see "cccc" (length 4), the original could have been "ccc", "cc", or "c" (3 possibilities). We sum these possibilities for all eligible groups.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    // Using a simple class for groups for clarity
    static class Group {
        char character;
        int count;
        Group(char character, int count) {
            this.character = character;
            this.count = count;
        }
    }

    public int findOriginalTypedString(String word) {
        if (word == null || word.isEmpty()) {
            return 0;
        }

        List<Group> groups = new ArrayList<>();
        for (char c : word.toCharArray()) {
            if (groups.isEmpty() || groups.get(groups.size() - 1).character != c) {
                groups.add(new Group(c, 1));
            } else {
                groups.get(groups.size() - 1).count++;
            }
        }

        int totalPossibilities = 1; // Case with no long press

        for (Group group : groups) {
            if (group.count > 1) {
                totalPossibilities += (group.count - 1);
            }
        }

        return totalPossibilities;
    }
}
```
### Algorithm
- Create a list to store groups of characters. A group can be represented by a pair or a small array, e.g., `(character, count)`.
- Iterate through the input `word` from the beginning.
- For each character, check if it's the same as the character of the last group added to the list.
- If it is, increment the count of the last group.
- If it's not, or if the list is empty, add a new group `(currentChar, 1)` to the list.
- After iterating through the entire word, initialize `totalPossibilities` to 1. This accounts for the case where no long press occurred.
- Iterate through the created list of groups.
- For each group `(char, count)`, if `count` is greater than 1, add `count - 1` to `totalPossibilities`.
- Return `totalPossibilities`.

## Single Pass Iteration
This is the most efficient approach, solving the problem in a single pass over the input string. It calculates the total number of possible original strings by identifying groups of consecutive characters and updating the total count on the fly, without needing any extra data structures to store the groups.
**Time:** O(N), where N is the length of `word`. Although there is a nested `while` loop, the outer pointer `i` is always updated to the position of the inner pointer `j`. This ensures that each character in the string is visited exactly once across all iterations. · **Space:** O(1). We only use a few variables to keep track of indices and the total count, regardless of the input size.
**Pros:** Extremely efficient in terms of space, using only a constant amount of extra memory.; Optimal time complexity as it processes the string in a single pass.
**Cons:** The nested loop structure, while efficient, might be slightly less intuitive at first glance compared to a two-step approach.
### Explanation
This approach combines the grouping and counting steps into a single, efficient pass. It maintains a running total of possibilities, initialized to 1 to account for the scenario with no typing errors.
As we iterate through the string, we identify the length of each consecutive character group. If a group's length, say `k`, is greater than 1, it implies this group could have been formed by a long press on a shorter sequence of the same character. The number of ways this could happen is `k-1`, which we add to our running total. By using a two-pointer technique, we can find the end of each group and continue the scan from the next new character, ensuring each character is processed only once.

```java
class Solution {
    public int findOriginalTypedString(String word) {
        if (word == null || word.length() == 0) {
            return 0;
        }
        int n = word.length();
        int totalPossibilities = 1; // Case with no long press
        int i = 0;
        while (i < n) {
            int j = i + 1;
            while (j < n && word.charAt(j) == word.charAt(i)) {
                j++;
            }
            // The group of identical characters is from index i to j-1
            int count = j - i;
            if (count > 1) {
                // This group could have been formed from a shorter sequence
                // of length 1, 2, ..., count-1. This gives count-1 possibilities.
                totalPossibilities += (count - 1);
            }
            // Move to the start of the next group
            i = j; 
        }
        return totalPossibilities;
    }
}
```
### Algorithm
- Initialize `totalPossibilities` to 1. This represents the case where the input `word` is the original string (no long presses).
- Initialize a pointer `i` to 0 to iterate through the string.
- Use a `while` loop that continues as long as `i` is less than the string length `n`.
- Inside the loop, use a second pointer `j` starting from `i + 1` to find the end of the current consecutive character group.
- The inner `while` loop increments `j` as long as `j < n` and `word.charAt(j)` is the same as `word.charAt(i)`.
- Once the inner loop finishes, the group of identical characters starts at `i` and ends at `j-1`. The length of this group is `count = j - i`.
- If `count` is greater than 1, it means this group could be the result of a long press. Add `count - 1` to `totalPossibilities`.
- Update the outer loop pointer `i` to `j` to move to the beginning of the next group.
- After the outer loop completes, return `totalPossibilities`.

# Solutions
### Python

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

```

### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```