3617. Find The Original Typed String I¶

LeetCode Problem View on GitHub

3617. Find the Original Typed String I

Easy

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:

Example 2:

Example 3:

Constraints:

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

Solution¶

class Solution {
    public int possibleStringCount(String word) {
        int n = word.length();
        Set<String> set = new HashSet<>();
        set.add(word); 
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && word.charAt(j) == word.charAt(i)) j++;
            int length = j - i;
            if (length > 1) {
                for (int k = 1; k < length; k++) {
                    String res = word.substring(0, i) + word.substring(i, i + k) + word.substring(j);
                    set.add(res);
                }
            }
            i = j;
        }
        return set.size();
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here