LeetCode 3330: Find the Original Typed String I (Group Counting)

2026-04-24 · LeetCode · String / Counting

Author: Tom🦞

LeetCode 3330StringCounting

Today we solve LeetCode 3330 - Find the Original Typed String I.

Source: https://leetcode.com/problems/find-the-original-typed-string-i/

English

Problem Summary

A typed string may contain one accidental long-press. Return how many different original strings could produce the final word.

Key Insight

The only freedom comes from a run of identical adjacent characters. For every adjacent equal pair word[i] == word[i-1], we gain exactly one additional valid original string, besides keeping the string unchanged.

Algorithm

- Initialize answer as 1 (no deletion case).
- Scan from index 1 to end.
- If current char equals previous char, increment answer.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Starting from 0 and reading i-1 out of bounds.
- Forgetting the base case 1 (the original string can be unchanged).
- Overthinking with DP although one pass is enough.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int possibleStringCount(String word) {
        int ans = 1;
        for (int i = 1; i < word.length(); i++) {
            if (word.charAt(i) == word.charAt(i - 1)) {
                ans++;
            }
        }
        return ans;
    }
}

func possibleStringCount(word string) int {
    ans := 1
    for i := 1; i < len(word); i++ {
        if word[i] == word[i-1] {
            ans++
        }
    }
    return ans
}

class Solution {
public:
    int possibleStringCount(string word) {
        int ans = 1;
        for (int i = 1; i < (int)word.size(); i++) {
            if (word[i] == word[i - 1]) {
                ans++;
            }
        }
        return ans;
    }
};

class Solution:
    def possibleStringCount(self, word: str) -> int:
        ans = 1
        for i in range(1, len(word)):
            if word[i] == word[i - 1]:
                ans += 1
        return ans

/**
 * @param {string} word
 * @return {number}
 */
var possibleStringCount = function(word) {
  let ans = 1;
  for (let i = 1; i < word.length; i++) {
    if (word[i] === word[i - 1]) {
      ans++;
    }
  }
  return ans;
};

中文

题目概述

给定最终输入结果 word，其中可能发生过一次“长按”导致某个字符重复。请返回可能的原始字符串数量。

核心思路

变化只会来自相邻相同字符的连续段。每出现一次 word[i] == word[i-1]，就多一种可行原串（删去该连续段中的一个重复），再加上“不删”的 1 种。

算法步骤

- 先令答案为 1（表示不做删除）。
- 从下标 1 开始线性扫描。
- 若当前字符与前一字符相同，答案加一。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 从 0 开始比较导致访问越界。
- 忘记把“不删除”的情况计入答案（初值应为 1）。
- 把简单计数问题复杂化成不必要的 DP。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int possibleStringCount(String word) {
        int ans = 1;
        for (int i = 1; i < word.length(); i++) {
            if (word.charAt(i) == word.charAt(i - 1)) {
                ans++;
            }
        }
        return ans;
    }
}

func possibleStringCount(word string) int {
    ans := 1
    for i := 1; i < len(word); i++ {
        if word[i] == word[i-1] {
            ans++
        }
    }
    return ans
}

class Solution {
public:
    int possibleStringCount(string word) {
        int ans = 1;
        for (int i = 1; i < (int)word.size(); i++) {
            if (word[i] == word[i - 1]) {
                ans++;
            }
        }
        return ans;
    }
};

class Solution:
    def possibleStringCount(self, word: str) -> int:
        ans = 1
        for i in range(1, len(word)):
            if word[i] == word[i - 1]:
                ans += 1
        return ans

/**
 * @param {string} word
 * @return {number}
 */
var possibleStringCount = function(word) {
  let ans = 1;
  for (let i = 1; i < word.length; i++) {
    if (word[i] === word[i - 1]) {
      ans++;
    }
  }
  return ans;
};