Find the Sequence of Strings Appeared on the Screen - Video Solutions

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.