LeetCode 3324 - Find the Sequence of Strings Appeared on the Screen

The problem gives us a target string and a very restricted keyboard with only two operations. The first key always appends the character "a" to the end of the current string. The second key changes only the last character of the current string to the next letter in the alphabet.

leetcodemediumstringsimulation

LeetCode Problem 3324

Difficulty: 🟡 Medium
Topics: String, Simulation

Solution

Problem Understanding

The problem gives us a target string and a very restricted keyboard with only two operations.

The first key always appends the character "a" to the end of the current string.

The second key changes only the last character of the current string to the next letter in the alphabet. For example:

  • "a" becomes "b"
  • "b" becomes "c"
  • "z" becomes "a"

Initially, the screen is empty, so the very first operation must be appending "a".

Our task is not just to produce the target string. We must return every intermediate string that appears on the screen while typing the target using the minimum possible number of key presses.

This detail is important because there can be many different sequences of operations, but only sequences with the minimum number of presses are valid.

For example, suppose the target is "he".

To produce the first character "h":

  • We first append "a"

  • Then rotate it repeatedly:

  • "b"

  • "c"

  • "d"

  • "e"

  • "f"

  • "g"

  • "h"

After reaching "h", we append another "a" to get "ha".

Then we rotate the last character until it becomes "e":

  • "hb"
  • "hc"
  • "hd"
  • "he"

The returned list must contain all of these visible strings in order.

The constraints are small:

  • 1 <= target.length <= 400
  • Only lowercase English letters appear

Since the alphabet size is fixed at 26, even a straightforward simulation is efficient enough.

An important observation is that every character must always begin as "a" because the only append operation adds "a". Therefore, to create a character like "m", we must append "a" and then apply the increment operation exactly 12 times.

Important edge cases include:

  • A single-character string
  • Characters equal to "a", because no increments are needed
  • Characters near "z", because many increments are required
  • Repeated characters such as "aaaa"
  • Strings where each character requires many rotations, such as "zzz"

Approaches

Brute Force Approach

A brute force mindset would try to explore all possible sequences of key presses and determine which ones produce the target using the minimum number of operations.

At every step, we could:

  • Append "a"
  • Increment the last character

We would continue generating states until the target appears. Then we would search among all possible operation sequences for those with minimum length.

This approach is theoretically correct because it explores the entire state space. However, it is extremely inefficient because the number of possible intermediate strings grows exponentially.

Even though the target length is at most 400, exploring all possible sequences is unnecessary because the operations behave very predictably.

Key Insight

The optimal strategy is deterministic.

To create each character in the target:

  1. Append "a" to extend the string length by one.
  2. Increment the last character until it matches the target character.

There is never a reason to overshoot or rotate through the alphabet unnecessarily because every extra increment increases the operation count.

For a target character c:

  • Appending "a" costs exactly one operation.
  • Converting "a" into c costs ord(c) - ord('a') increment operations.

This is clearly minimal.

Therefore, we can directly simulate the optimal process and record every visible string.

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Explores all possible operation sequences
Optimal O(n * 26) O(n * 26) Directly simulates the minimum operation sequence

Since the alphabet size is constant, the practical complexity is effectively linear.

Algorithm Walkthrough

  1. Initialize an empty result list that will store every string appearing on the screen.
  2. Initialize an empty current string. This represents the current state of the screen.
  3. Iterate through each character target_char in the target string.
  4. Append "a" to the current string because the only way to increase the string length is by pressing key 1.
  5. Add the new string to the result list because every intermediate screen state must be recorded.
  6. Determine how many increments are needed to transform the last character from "a" into target_char.
  7. Repeatedly increment the last character:
  • Replace the final character with the next alphabet character.
  • Append the updated string to the result list after every increment.
  1. Continue until the last character matches the target character.
  2. After processing all characters, return the result list.

Why it works

The algorithm is correct because every new character must begin as "a", since key 1 always appends "a".

To transform "a" into a target character c, the minimum number of increments is exactly the alphabetical distance from "a" to c.

Since the algorithm performs exactly these required operations and records every intermediate screen state, it produces the correct sequence using the minimum possible number of key presses.

Python Solution

from typing import List

class Solution:
    def stringSequence(self, target: str) -> List[str]:
        result = []
        current = []

        for target_char in target:
            current.append('a')
            result.append(''.join(current))

            while current[-1] != target_char:
                current[-1] = chr(ord(current[-1]) + 1)
                result.append(''.join(current))

        return result

The implementation closely follows the simulation process described earlier.

The current list stores the current screen state as mutable characters. Using a list is more efficient than repeatedly rebuilding immutable Python strings.

For every target character:

  • We append 'a'
  • Record the resulting string
  • Increment the last character until it matches the target character

Each intermediate state is converted into a string using ''.join(current) and appended to the result list.

The loop:

while current[-1] != target_char:

guarantees that we stop immediately after reaching the desired character, ensuring the minimum number of operations.

Go Solution

func stringSequence(target string) []string {
    result := []string{}
    current := []byte{}

    for i := 0; i < len(target); i++ {
        targetChar := target[i]

        current = append(current, 'a')
        result = append(result, string(current))

        for current[len(current)-1] != targetChar {
            current[len(current)-1]++
            result = append(result, string(current))
        }
    }

    return result
}

The Go implementation uses a []byte slice for efficient in-place character modification.

Unlike Python strings, Go strings are immutable, so modifying characters directly would not be possible without converting to a mutable structure. Using a byte slice allows efficient updates to the last character.

Each time the current state changes, it is converted to a string and appended to the result slice.

No overflow concerns exist because the problem guarantees lowercase English letters, and the optimal process never requires wrapping from 'z' back to 'a'.

Worked Examples

Example 1

Input:

target = "abc"

Step-by-step execution:

Step Operation Current String Result List
1 Append 'a' "a" ["a"]
2 Append 'a' "aa" ["a","aa"]
3 Increment last char "ab" ["a","aa","ab"]
4 Append 'a' "aba" ["a","aa","ab","aba"]
5 Increment last char "abb" ["a","aa","ab","aba","abb"]
6 Increment last char "abc" ["a","aa","ab","aba","abb","abc"]

Final output:

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

Example 2

Input:

target = "he"

Step-by-step execution:

Step Operation Current String
1 Append 'a' "a"
2 Increment "b"
3 Increment "c"
4 Increment "d"
5 Increment "e"
6 Increment "f"
7 Increment "g"
8 Increment "h"
9 Append 'a' "ha"
10 Increment "hb"
11 Increment "hc"
12 Increment "hd"
13 Increment "he"

Final output:

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

Complexity Analysis

Measure Complexity Explanation
Time O(n * 26) Each character may require up to 25 increments
Space O(n * 26) The result list stores all intermediate strings

The alphabet size is fixed at 26, so each target character requires at most 25 increment operations after one append operation.

Therefore, the total number of generated strings is bounded by 26 * n, making the algorithm effectively linear relative to the target length.

The output itself can contain up to 26 * n strings, so the space complexity is naturally proportional to the output size.

Test Cases

from typing import List

class Solution:
    def stringSequence(self, target: str) -> List[str]:
        result = []
        current = []

        for target_char in target:
            current.append('a')
            result.append(''.join(current))

            while current[-1] != target_char:
                current[-1] = chr(ord(current[-1]) + 1)
                result.append(''.join(current))

        return result

sol = Solution()

# Provided example 1
assert sol.stringSequence("abc") == [
    "a", "aa", "ab", "aba", "abb", "abc"
]

# Provided example 2
assert sol.stringSequence("he") == [
    "a", "b", "c", "d", "e", "f", "g", "h",
    "ha", "hb", "hc", "hd", "he"
]

# Single character already equal to 'a'
assert sol.stringSequence("a") == ["a"]

# Single character near end of alphabet
assert sol.stringSequence("z") == [
    "a", "b", "c", "d", "e", "f", "g", "h",
    "i", "j", "k", "l", "m", "n", "o", "p",
    "q", "r", "s", "t", "u", "v", "w", "x",
    "y", "z"
]

# Repeated characters requiring no increments
assert sol.stringSequence("aaa") == [
    "a", "aa", "aaa"
]

# Mixed characters
assert sol.stringSequence("az") == [
    "a",
    "aa", "ab", "ac", "ad", "ae", "af", "ag",
    "ah", "ai", "aj", "ak", "al", "am", "an",
    "ao", "ap", "aq", "ar", "as", "at", "au",
    "av", "aw", "ax", "ay", "az"
]

# Repeated high-cost characters
result = sol.stringSequence("zzz")
assert result[-1] == "zzz"  # Final target reached
assert len(result) == 78    # 26 states per character
Test Why
"abc" Validates the standard incremental process
"he" Tests many increments before appending next character
"a" Smallest valid input
"z" Maximum increments for one character
"aaa" Ensures no unnecessary increments occur
"az" Mixes zero-cost and high-cost characters
"zzz" Stress test with maximum increments repeatedly

Edge Cases

Target Contains Only 'a'

A string like "aaaa" is important because no increment operations are needed after appending each character.

A buggy implementation might still attempt unnecessary rotations. The current solution correctly stops immediately because the while loop condition fails instantly when the appended character already matches the target character.

Target Contains Characters Near 'z'

Characters like 'y' and 'z' require many increment operations.

This is important because off-by-one errors are common when repeatedly modifying characters. The implementation carefully increments until the current character exactly matches the target character, ensuring correctness even at the end of the alphabet.

Single Character Input

A one-character target such as "c" is the smallest nontrivial case.

Some implementations accidentally assume multiple append operations or mishandle initialization logic. The current solution handles this naturally because the loop processes every target character independently, even when the length is one.