Skip to content

3324. Find the Sequence of Strings Appeared on the Screen

Description

You are given a string target.

Alice is going to type target on her computer using a special keyboard that has only two keys:

  • Key 1 appends the character "a" to the string on the screen.
  • Key 2 changes the last character of the string on the screen to its next character in the English alphabet. For example, "c" changes to "d" and "z" changes to "a".

Note that initially there is an empty string "" on the screen, so she can only press key 1.

Return a list of all strings that appear on the screen as Alice types target, in the order they appear, using the minimum key presses.

 

Example 1:

Input: target = "abc"

Output: ["a","aa","ab","aba","abb","abc"]

Explanation:

The sequence of key presses done by Alice are:

  • Press key 1, and the string on the screen becomes "a".
  • Press key 1, and the string on the screen becomes "aa".
  • Press key 2, and the string on the screen becomes "ab".
  • Press key 1, and the string on the screen becomes "aba".
  • Press key 2, and the string on the screen becomes "abb".
  • Press key 2, and the string on the screen becomes "abc".

Example 2:

Input: target = "he"

Output: ["a","b","c","d","e","f","g","h","ha","hb","hc","hd","he"]

 

Constraints:

  • 1 <= target.length <= 400
  • target consists only of lowercase English letters.

Solutions

Solution 1: Simulation

Thinking

The screen starts empty; each key appends a letter or advances the last one. With \(|\textit{target}| \le 400\), we can simulate letter by letter.

For each target character we append \(\texttt{a}\), then \(\texttt{b}\), and so on onto the current prefix until that character appears. Every intermediate string is part of the required sequence.

No search over keypresses is needed: walking \(\textit{ascii\_lowercase}\) up to the target letter records every screen state.

We can simulate Alice's typing process, starting from an empty string and updating the string after each keystroke until the target string is obtained.

The time complexity is \(O(n^2 \times |\Sigma|)\), where \(n\) is the length of the target string and \(\Sigma\) is the character set, which in this case is the set of lowercase letters, so \(|\Sigma| = 26\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def stringSequence(self, target: str) -> List[str]:
        ans = []
        for c in target:
            s = ans[-1] if ans else ""
            for a in ascii_lowercase:
                t = s + a
                ans.append(t)
                if a == c:
                    break
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public List<String> stringSequence(String target) {
        List<String> ans = new ArrayList<>();
        for (char c : target.toCharArray()) {
            String s = ans.isEmpty() ? "" : ans.get(ans.size() - 1);
            for (char a = 'a'; a <= c; ++a) {
                String t = s + a;
                ans.add(t);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    vector<string> stringSequence(string target) {
        vector<string> ans;
        for (char c : target) {
            string s = ans.empty() ? "" : ans.back();
            for (char a = 'a'; a <= c; ++a) {
                string t = s + a;
                ans.push_back(t);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func stringSequence(target string) (ans []string) {
    for _, c := range target {
        s := ""
        if len(ans) > 0 {
            s = ans[len(ans)-1]
        }
        for a := 'a'; a <= c; a++ {
            t := s + string(a)
            ans = append(ans, t)
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function stringSequence(target: string): string[] {
    const ans: string[] = [];
    for (const c of target) {
        let s = ans.length > 0 ? ans[ans.length - 1] : '';
        for (let a = 'a'.charCodeAt(0); a <= c.charCodeAt(0); a++) {
            const t = s + String.fromCharCode(a);
            ans.push(t);
        }
    }
    return ans;
}

Comments