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.

Examples

Example 1

1
2
3
4
5

Input: word = "abbcccc"
Output: 5
Explanation:
The possible strings are: `"abbcccc"`, `"abbccc"`, `"abbcc"`, `"abbc"`, and
`"abcccc"`.

Example 2

1
2
3
4

Input: word = "abcd"
Output: 1
Explanation:
The only possible string is `"abcd"`.

Example 3

1
2

Input: word = "aaaa"
Output: 4

Constraints

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

Solution

Method 1 – Group Counting and Single Expansion

Intuition

Since Alice may have pressed a key for too long at most once, the original string can be obtained by reducing the length of any one group of consecutive characters by any amount (including not reducing it at all). For each group, we can try all possible reductions (removing 0 up to all but one character from the group), and count the total number of unique original strings.

Approach

  1. Group the string into consecutive runs of the same character.
  2. For each group, consider reducing its length by any amount (from 0 up to the group length minus 1), but only for one group (since at most one long press).
  3. For each group, generate the possible original strings by reducing that group, and add them to a set.
  4. Always include the original string (no reduction).
  5. Return the size of the set.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    int possibleStringCount(std::string word) {
        std::vector<std::pair<char, int>> groups;
        int n = word.size(), i = 0;
        while (i < n) {
            int j = i;
            while (j < n && word[j] == word[i]) ++j;
            groups.push_back({word[i], j - i});
            i = j;
        }
        std::set<std::string> st;
        // Original string
        std::string orig;
        for (auto& [c, cnt] : groups) orig += std::string(cnt, c);
        st.insert(orig);
        for (int g = 0; g < groups.size(); ++g) {
            for (int reduce = 1; reduce < groups[g].second; ++reduce) {
                std::string s;
                for (int k = 0; k < groups.size(); ++k) {
                    int len = groups[k].second;
                    if (k == g) len -= reduce;
                    s += std::string(len, groups[k].first);
                }
                st.insert(s);
            }
        }
        return st.size();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func possibleStringCount(word string) int {
    type group struct{c byte; cnt int}
    n := len(word)
    groups := []group{}
    for i := 0; i < n; {
        j := i
        for j < n && word[j] == word[i] {j++}
        groups = append(groups, group{word[i], j-i})
        i = j
    }
    st := map[string]struct{}{}
    orig := ""
    for _, g := range groups {
        for k := 0; k < g.cnt; k++ { orig += string(g.c) }
    }
    st[orig] = struct{}{}
    for g := range groups {
        for reduce := 1; reduce < groups[g].cnt; reduce++ {
            s := ""
            for k := range groups {
                l := groups[k].cnt
                if k == g { l -= reduce }
                for t := 0; t < l; t++ { s += string(groups[k].c) }
            }
            st[s] = struct{}{}
        }
    }
    return len(st)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public int possibleStringCount(String word) {
        List<int[]> groups = new ArrayList<>();
        int n = word.length(), i = 0;
        while (i < n) {
            int j = i;
            while (j < n && word.charAt(j) == word.charAt(i)) ++j;
            groups.add(new int[]{word.charAt(i), j - i});
            i = j;
        }
        Set<String> st = new HashSet<>();
        StringBuilder orig = new StringBuilder();
        for (int[] g : groups) for (int k = 0; k < g[1]; ++k) orig.append((char)g[0]);
        st.add(orig.toString());
        for (int g = 0; g < groups.size(); ++g) {
            for (int reduce = 1; reduce < groups.get(g)[1]; ++reduce) {
                StringBuilder sb = new StringBuilder();
                for (int k = 0; k < groups.size(); ++k) {
                    int len = groups.get(k)[1];
                    if (k == g) len -= reduce;
                    for (int t = 0; t < len; ++t) sb.append((char)groups.get(k)[0]);
                }
                st.add(sb.toString());
            }
        }
        return st.size();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    fun possibleStringCount(word: String): Int {
        val groups = mutableListOf<Pair<Char, Int>>()
        var i = 0
        while (i < word.length) {
            var j = i
            while (j < word.length && word[j] == word[i]) j++
            groups.add(word[i] to (j - i))
            i = j
        }
        val st = mutableSetOf<String>()
        val orig = buildString { for ((c, cnt) in groups) append(c.toString().repeat(cnt)) }
        st.add(orig)
        for (g in groups.indices) {
            for (reduce in 1 until groups[g].second) {
                val s = buildString {
                    for ((k, group) in groups.withIndex()) {
                        var len = group.second
                        if (k == g) len -= reduce
                        append(group.first.toString().repeat(len))
                    }
                }
                st.add(s)
            }
        }
        return st.size
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def possibleStringCount(self, word: str) -> int:
        n = len(word)
        groups = []
        i = 0
        while i < n:
            j = i
            while j < n and word[j] == word[i]:
                j += 1
            groups.append((word[i], j - i))
            i = j
        st = set()
        orig = ''.join(c * cnt for c, cnt in groups)
        st.add(orig)
        for g, (c, cnt) in enumerate(groups):
            for reduce in range(1, cnt):
                s = ''.join(
                    (c2 * (cnt2 - reduce) if k == g else c2 * cnt2)
                    for k, (c2, cnt2) in enumerate(groups)
                )
                st.add(s)
        return len(st)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

impl Solution {
    pub fn possible_string_count(word: String) -> i32 {
        let n = word.len();
        let bytes = word.as_bytes();
        let mut groups = vec![];
        let mut i = 0;
        while i < n {
            let mut j = i;
            while j < n && bytes[j] == bytes[i] { j += 1; }
            groups.push((bytes[i], j - i));
            i = j;
        }
        use std::collections::HashSet;
        let mut st = HashSet::new();
        let mut orig = Vec::new();
        for &(c, cnt) in &groups {
            for _ in 0..cnt { orig.push(c); }
        }
        st.insert(orig.clone());
        for g in 0..groups.len() {
            for reduce in 1..groups[g].1 {
                let mut s = Vec::new();
                for (k, &(c, cnt)) in groups.iter().enumerate() {
                    let len = if k == g { cnt - reduce } else { cnt };
                    for _ in 0..len { s.push(c); }
                }
                st.insert(s);
            }
        }
        st.len() as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    possibleStringCount(word: string): number {
        const groups: [string, number][] = [];
        let i = 0;
        while (i < word.length) {
            let j = i;
            while (j < word.length && word[j] === word[i]) j++;
            groups.push([word[i], j - i]);
            i = j;
        }
        const st = new Set<string>();
        const orig = groups.map(([c, cnt]) => c.repeat(cnt)).join('');
        st.add(orig);
        for (let g = 0; g < groups.length; ++g) {
            for (let reduce = 1; reduce < groups[g][1]; ++reduce) {
                let s = '';
                for (let k = 0; k < groups.length; ++k) {
                    let len = groups[k][1];
                    if (k === g) len -= reduce;
                    s += groups[k][0].repeat(len);
                }
                st.add(s);
            }
        }
        return st.size;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) — For each group, we may generate up to n variants, and each string is up to length n.
  • 🧺 Space complexity: O(n^2) — For the set of possible strings.