You are given a string target.
Alice is going to type target on her computer using a special keyboard that has only two keys:
"a" to the string on the screen."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:
"a"."aa"."ab"."aba"."abb"."abc".Example 2:
Input: target = "he"
Output: ["a","b","c","d","e","f","g","h","ha","hb","hc","hd","he"]
Constraints:
1 <= target.length <= 400target consists only of lowercase English letters.Problem Overview: You are given a target string and must return every intermediate string that appears on the screen while typing it using a restricted keyboard. The keyboard starts with the string "a". Two operations are allowed: append 'a' to the end, or increment the last character to the next letter in the alphabet. The task is to simulate the typing process until the screen matches the target string.
Approach 1: Iterative String Construction (O(26 * n) time, O(n) space)
This approach directly simulates the screen operations using a mutable string. Start with "a" and store it in the result list. For each position i in the target, repeatedly increment the last character until it equals target[i]. After every increment, push the current string into the result. Once the correct character is reached, append 'a' if there are more characters left in the target, and record the new string again. Each character may be incremented at most 25 times, so the overall time complexity is O(26 * n), which simplifies to O(n). This approach is straightforward and mirrors the exact behavior described in the problem statement, making it easy to reason about during interviews.
Approach 2: Optimized Approach with Direct Character Manipulation (O(26 * n) time, O(n) space)
Instead of repeatedly rebuilding immutable strings, maintain a character array representing the current screen state. Modify the last character directly in the array while performing the increment operation. After each update, convert the array to a string and append it to the output list. This avoids repeated string allocations during intermediate steps and keeps operations cache‑friendly. The logic remains the same: iterate through the target characters, increment the last character until it matches, then append 'a' for the next position. Time complexity remains O(26 * n) because each position may require up to 25 increments, while space complexity stays O(n) for storing the result.
The problem mainly tests careful simulation and basic manipulation of a string. The key observation is that every character always starts as 'a' and moves forward alphabetically until it matches the target.
Recommended for interviews: The iterative simulation approach is usually what interviewers expect. It shows you can translate a process description into code and manage intermediate states correctly. The optimized character-array variant demonstrates awareness of string mutability and performance tradeoffs, which can matter in languages where strings are immutable.
This approach involves simulating each key press step by step. Begin with an empty string and use Key 1 to add characters or Key 2 to change the last character until the target is achieved.
Iteratively compare each target character with the current screen character to decide whether to append or modify with Key 2.
In this C implementation, we simulate each step by maintaining a string current that represents the content on the screen at any time.
For each step, we append 'a' using Key 1 and subsequently change the character to match the target using Key 2.
Time Complexity: O(n * 26), where n is the length of the string because, for each character, in the worst case, you might need to press Key 2 up to 26 times.
Space Complexity: O(n^2) for storing the intermediate strings.
An optimized approach focuses on noticing that each time Key 1 is used, it adds 'a', and any further changes with Key 2 depends on the target character. Thus, compute the difference directly and assemble the sequence more directly without individually adding each character.
This C implementation manually computes the letter transformation count by directly evaluating character differences.
This adjusts string states more directly and concisely.
Time Complexity: O(n) per string, focusing directly on character differences.
Space Complexity: O(n^2) as still recording multiple states.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Iterative String Construction | Time Complexity: Space Complexity: |
| Optimized Approach with Direct Character Manipulation | Time Complexity: Space Complexity: |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative String Construction | O(26 * n) ≈ O(n) | O(n) | Best for clarity and interview explanations where direct simulation is expected |
| Direct Character Manipulation (Array Based) | O(26 * n) ≈ O(n) | O(n) | When optimizing string updates in languages with immutable strings |
Find the Sequence of Strings Appeared on the Screen || LeetCode Weekly Contest 420 • codi • 1,471 views views
Watch 5 more video solutions →Practice Find the Sequence of Strings Appeared on the Screen with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor