Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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

1
2
3
4


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.

Solution

Method 1 – Simulation with Greedy Key Presses

Intuition

To type the target string with the minimum key presses, always append ‘a’ until the next character can be reached by incrementing the last character. For each character, if it is ‘a’, append; otherwise, append ‘a’ and increment the last character as needed.

Approach

  1. Start with an empty string.
  2. For each character in target:
    • If the string is empty, append ‘a’.
    • While the last character is not equal to the target character, increment the last character (wrap ‘z’ to ‘a’).
    • After each operation, record the current string.
  3. Continue until the target is built.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<string> getSmallestSequence(string target) {
        vector<string> ans;
        string s = "";
        for (char c : target) {
            if (s.empty()) {
                s += 'a';
                ans.push_back(s);
            }
            while (s.back() != c) {
                s.back() = (s.back() == 'z' ? 'a' : s.back() + 1);
                ans.push_back(s);
            }
            if (s.size() < target.size()) {
                s += 'a';
                ans.push_back(s);
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func getSmallestSequence(target string) []string {
    ans := []string{}
    s := ""
    for i := 0; i < len(target); i++ {
        c := target[i]
        if len(s) == 0 {
            s += "a"
            ans = append(ans, s)
        }
        for s[len(s)-1] != c {
            if s[len(s)-1] == 'z' {
                s = s[:len(s)-1] + "a"
            } else {
                s = s[:len(s)-1] + string(s[len(s)-1]+1)
            }
            ans = append(ans, s)
        }
        if len(s) < len(target) {
            s += "a"
            ans = append(ans, s)
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public List<String> getSmallestSequence(String target) {
        List<String> ans = new ArrayList<>();
        StringBuilder s = new StringBuilder();
        for (char c : target.toCharArray()) {
            if (s.length() == 0) {
                s.append('a');
                ans.add(s.toString());
            }
            while (s.charAt(s.length() - 1) != c) {
                char last = s.charAt(s.length() - 1);
                last = (last == 'z') ? 'a' : (char)(last + 1);
                s.setCharAt(s.length() - 1, last);
                ans.add(s.toString());
            }
            if (s.length() < target.length()) {
                s.append('a');
                ans.add(s.toString());
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun getSmallestSequence(target: String): List<String> {
        val ans = mutableListOf<String>()
        val s = StringBuilder()
        for (c in target) {
            if (s.isEmpty()) {
                s.append('a')
                ans.add(s.toString())
            }
            while (s.last() != c) {
                s.setCharAt(s.length - 1, if (s.last() == 'z') 'a' else s.last() + 1)
                ans.add(s.toString())
            }
            if (s.length < target.length) {
                s.append('a')
                ans.add(s.toString())
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def getSmallestSequence(self, target: str) -> list[str]:
        ans = []
        s = ''
        for c in target:
            if not s:
                s += 'a'
                ans.append(s)
            while s[-1] != c:
                s = s[:-1] + (chr(ord('a') if s[-1] == 'z' else ord(s[-1]) + 1))
                ans.append(s)
            if len(s) < len(target):
                s += 'a'
                ans.append(s)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn get_smallest_sequence(target: String) -> Vec<String> {
        let mut ans = Vec::new();
        let mut s = String::new();
        for c in target.chars() {
            if s.is_empty() {
                s.push('a');
                ans.push(s.clone());
            }
            while s.chars().last().unwrap() != c {
                let mut chars: Vec<char> = s.chars().collect();
                chars[chars.len() - 1] = if chars[chars.len() - 1] == 'z' { 'a' } else { ((chars[chars.len() - 1] as u8) + 1) as char };
                s = chars.into_iter().collect();
                ans.push(s.clone());
            }
            if s.len() < target.len() {
                s.push('a');
                ans.push(s.clone());
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    getSmallestSequence(target: string): string[] {
        const ans: string[] = [];
        let s = '';
        for (const c of target) {
            if (!s) {
                s += 'a';
                ans.push(s);
            }
            while (s[s.length - 1] !== c) {
                s = s.slice(0, -1) + (s[s.length - 1] === 'z' ? 'a' : String.fromCharCode(s.charCodeAt(s.length - 1) + 1));
                ans.push(s);
            }
            if (s.length < target.length) {
                s += 'a';
                ans.push(s);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n * 26) — For each character, at most 26 increments.
  • 🧺 Space complexity: O(n^2) — For the output list of strings.