# Find the Sequence of Strings Appeared on the Screen
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-sequence-of-strings-appeared-on-the-screen)
Canonical: https://scaleengineer.com/dsa/problems/find-the-sequence-of-strings-appeared-on-the-screen
**Data structures:** String
---
## 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.

**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.

# Approaches
## Naive Simulation with String Concatenation
This approach directly simulates the process of typing the target string using basic string operations. For each character of the target, it first appends an 'a' and then repeatedly modifies the last character until it matches the target character. The simulation relies on standard string concatenation and substring methods, which are known to be inefficient for sequential modifications as they create new string objects for every change.
**Time:** O(N^2), where N is the length of the `target` string. For each of the `N` characters in `target`, we perform operations. The string length grows up to `N`. String concatenation and substring operations take time proportional to the string length (`O(i)` at step `i`). The total time is dominated by these operations inside the loops, leading to a complexity of `sum_{i=1 to N} O(i) = O(N^2)`. · **Space:** O(N^2), where N is the length of the `target` string. The `result` list stores all intermediate strings. The number of strings is at most `N * 26`, and their lengths go up to `N`. The total number of characters stored is on the order of `sum_{i=1 to N} i`, which is `O(N^2)`.
**Pros:** The logic is very straightforward and directly maps to the problem's description.; It's easy to implement using basic language features without needing specialized classes like `StringBuilder`.
**Cons:** Highly inefficient in terms of performance due to the properties of immutable strings in Java. Each concatenation or substring operation creates a new string object, leading to significant memory allocation and garbage collection overhead.; The time complexity has a large constant factor, making it much slower in practice than a `StringBuilder`-based solution for the same asymptotic complexity.
### Explanation
The algorithm maintains the current string on the screen as a standard Java `String` object. It iterates through the `target` string, and for each character, it first performs an append operation by concatenating `"a"`. This new string is added to our results. Then, it enters a loop to transform the newly appended 'a' into the required target character. Inside this loop, it repeatedly calculates the next character in the alphabet and reconstructs the entire string by taking a substring of the current string (all but the last character) and appending the new character. This reconstructed string is also added to the results. This process continues until the last character matches the target character. While simple to conceptualize, this method is suboptimal because creating new string objects in a loop is computationally expensive.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> findSequence(String target) {
        List<String> result = new ArrayList<>();
        if (target == null || target.length() == 0) {
            return result;
        }

        String currentString = "";
        for (char targetChar : target.toCharArray()) {
            // Press key 1: append 'a'
            currentString = currentString + "a";
            result.add(currentString);

            // Press key 2: modify last character
            char lastChar = 'a';
            while (lastChar < targetChar) {
                lastChar++;
                currentString = currentString.substring(0, currentString.length() - 1) + lastChar;
                result.add(currentString);
            }
        }
        return result;
    }
}
```
### Algorithm
1. Initialize an empty list of strings, `result`, to store the output sequence.
2. Initialize an empty string, `currentString`, to represent the string on the screen.
3. Iterate through each character `targetChar` of the input `target` string.
4. For each `targetChar`:
    a. Simulate pressing Key 1: Append 'a' to `currentString` using string concatenation (`currentString = currentString + "a"`).
    b. Add the new `currentString` to the `result` list.
    c. Simulate pressing Key 2: Start with the last character as 'a'. While it is less than `targetChar`, increment the character and update `currentString`.
    d. The update step involves creating a new string by taking a substring of the old one and concatenating the new last character: `currentString = currentString.substring(0, currentString.length() - 1) + newChar`.
    e. Add each intermediate string to the `result` list.
5. After iterating through all characters of `target`, return the `result` list.

## Optimized Simulation with StringBuilder
This approach follows the same simulation logic but employs a `StringBuilder` to manage the string on the screen. A `StringBuilder` is a mutable sequence of characters, allowing for efficient modifications such as appending a character or changing a character at a specific index. By using `StringBuilder`, we avoid the significant overhead of creating new string objects for every small change, which makes this the most efficient and optimal solution.
**Time:** O(N^2), where N is the length of the `target` string. The dominant operation is `sb.toString()`, which is called for every intermediate string and takes time proportional to the string's current length (`O(i)` at step `i`). The total time complexity is the sum of the lengths of all generated strings, which is `O(N^2)`. This is optimal because the size of the required output is `O(N^2)`. · **Space:** O(N^2), where N is the length of the `target` string. The space is dominated by the `result` list, which must store a sequence of strings whose total character count is `O(N^2)`. The `StringBuilder` itself uses `O(N)` space.
**Pros:** This is the most efficient solution in practice. `StringBuilder` operations like `append` and `setCharAt` are very fast (amortized O(1) and O(1) respectively).; It minimizes memory allocations and garbage collection overhead compared to the naive string concatenation approach.; The algorithm is asymptotically optimal, as its runtime is dictated by the size of the output.
**Cons:** The asymptotic time and space complexity are bound by the `O(N^2)` size of the output, so no further asymptotic improvements are possible.
### Explanation
The core idea is to replace the inefficient `String` concatenations with a mutable `StringBuilder`. We start with an empty `StringBuilder`. For each character in the `target` string, we first append 'a' using the `append()` method, which is an amortized constant-time operation. We then convert the `StringBuilder` to a `String` and add it to our result list. Next, we repeatedly modify the last character to match the `targetChar`. This is done efficiently using `setCharAt()`, which is a constant-time operation. After each modification, we again convert the `StringBuilder` to a `String` for the result list. The most time-consuming part of this process is the `toString()` conversion, which takes time proportional to the current string length. Since the output size itself is `O(N^2)`, an algorithm with this time complexity is optimal.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> findSequence(String target) {
        List<String> result = new ArrayList<>();
        if (target == null || target.length() == 0) {
            return result;
        }

        StringBuilder sb = new StringBuilder();
        for (char targetChar : target.toCharArray()) {
            // Press key 1: append 'a'
            sb.append('a');
            result.add(sb.toString());

            // Press key 2: modify last character
            while (sb.charAt(sb.length() - 1) < targetChar) {
                char newLastChar = (char) (sb.charAt(sb.length() - 1) + 1);
                sb.setCharAt(sb.length() - 1, newLastChar);
                result.add(sb.toString());
            }
        }
        return result;
    }
}
```
### Algorithm
1. Initialize an empty list of strings, `result`.
2. Initialize an empty `StringBuilder`, `sb`, to efficiently build and modify the string on the screen.
3. Iterate through each character `targetChar` of the input `target` string.
4. For each `targetChar`:
    a. Simulate pressing Key 1: Append 'a' to `sb` using `sb.append('a')`.
    b. Add the current string to the results: `result.add(sb.toString())`.
    c. Simulate pressing Key 2: Loop as long as the last character in `sb` does not match `targetChar`.
    d. Inside the loop, get the last character, increment it, and update it in-place using `sb.setCharAt(sb.length() - 1, newChar)`.
    e. Add the modified string to the results: `result.add(sb.toString())`.
5. After the loops complete, return the `result` list.

# Solutions
### Java

```java
class Solution {
public
  List<String> stringSequence(String target) {
    List<String> ans = new ArrayList<>();
    for (char c : target.toCharArray()) {
      String s = ans.isEmpty() ? "" : ans.get(ans.size() - 1);
      for (char a = 'a'; a <= c; ++a) {
        String t = s + a;
        ans.add(t);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<string> stringSequence(string target) {
    vector<string> ans;
    for (char c : target) {
      string s = ans.empty() ? "" : ans.back();
      for (char a = 'a'; a <= c; ++a) {
        string t = s + a;
        ans.push_back(t);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def stringSequence(self, target: str) -> List[str]: ans = [] for c in target: s = ans[- 1] if ans else "" for a in ascii_lowercase: t = s + a ans . append(t) if a == c: break return ans

```