Skip to main content
Talentd

Find the Sequence of Strings Appeared on the Screen - Solution & Explanation

MediumStringSimulation15 min readAsked at: Bloomberg
Practice this problem

Problem Statement

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.

Approach Overview

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.

Approach 1: Iterative String Construction

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Optimized Approach with Direct Character Manipulation

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) per string, focusing directly on character differences.

Space Complexity: O(n^2) as still recording multiple states.

Try this approach in the editor →

Approach 3: Simulation

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative String Construction

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.

Optimized Approach with Direct Character Manipulation

Time Complexity: O(n) per string, focusing directly on character differences.

Space Complexity: O(n^2) as still recording multiple states.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative String ConstructionO(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

Video Solution

Find the Sequence of Strings Appeared on the Screen || LeetCode Weekly Contest 420 • codi • 1,471 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Find the Sequence of Strings Appeared on the Screen easy or hard?
The problem is generally rated Medium because it requires careful simulation and tracking of intermediate states. The algorithm itself is straightforward, but missing small steps in the process can lead to incorrect sequences.
Find the Sequence of Strings Appeared on the Screen Python/Java solution
In Python or Java, maintain a current string (or character array) and simulate the operations. Increment the last character until it equals the target character, storing each intermediate result, then append 'a' when moving to the next index. Both implementations run in O(n) effective time and O(n) space.
How to solve Find the Sequence of Strings Appeared on the Screen in O(n)?
Simulate the screen operations using a current string or character array. For each target character, repeatedly increment the last character until it matches the target, recording every intermediate state. Then append 'a' to start constructing the next position. Because each character increases at most 25 times, the total runtime is linear in the target length.
What is the best approach for Find the Sequence of Strings Appeared on the Screen?
The best approach is direct simulation of the typing process. Start with the string "a", increment the last character until it matches the target character, and append 'a' when moving to the next position. This approach runs in O(26 * n) time, effectively O(n), and uses O(n) space for storing the sequence of intermediate strings.
Is Find the Sequence of Strings Appeared on the Screen asked at Google/Amazon/Meta?
This style of problem appears in interviews at companies like Amazon, Google, and Meta when testing simulation and string manipulation skills. While the exact problem may vary, candidates are often asked to model a process step-by-step and track intermediate states efficiently.
What data structure is used in Find the Sequence of Strings Appeared on the Screen?
The core data structures are a string or a mutable character array to represent the current screen content, and a list or array to store all intermediate strings. The algorithm mainly relies on string manipulation and simple iteration.
What is the time complexity of Find the Sequence of Strings Appeared on the Screen?
The time complexity is O(26 * n), where n is the length of the target string. Each position may require up to 25 increments to reach the desired character from 'a'. Since 26 is a constant alphabet size, the complexity simplifies to O(n). Space complexity is O(n) for storing the resulting sequence of strings.

Ready to solve this problem?

Practice Find the Sequence of Strings Appeared on the Screen with our built-in code editor and test cases.

Practice on FleetCode
Previous

Keyboard Row