Find the Sequence of Strings Appeared on the Screen

Med

#2952Time: 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)`.

Data structures

String

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

Initialize an empty list of strings, result, to store the output sequence.
Initialize an empty string, currentString, to represent the string on the screen.
Iterate through each character targetChar of the input target string.
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.
After iterating through all characters of target, return the result list.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<String> findSequence(String target) {6        List<String> result = new ArrayList<>();7        if (target == null || target.length() == 0) {8            return result;9        }10 11        String currentString = "";12        for (char targetChar : target.toCharArray()) {13            // Press key 1: append 'a'14            currentString = currentString + "a";15            result.add(currentString);16 17            // Press key 2: modify last character18            char lastChar = 'a';19            while (lastChar < targetChar) {20                lastChar++;21                currentString = currentString.substring(0, currentString.length() - 1) + lastChar;22                result.add(currentString);23            }24        }25        return result;26    }27}

Complexity

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)`.

Trade-offs

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.

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.

Algorithm

Initialize an empty list of strings, result.
Initialize an empty StringBuilder, sb, to efficiently build and modify the string on the screen.
Iterate through each character targetChar of the input target string.
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()).
After the loops complete, return the result list.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<String> findSequence(String target) {6        List<String> result = new ArrayList<>();7        if (target == null || target.length() == 0) {8            return result;9        }10 11        StringBuilder sb = new StringBuilder();12        for (char targetChar : target.toCharArray()) {13            // Press key 1: append 'a'14            sb.append('a');15            result.add(sb.toString());16 17            // Press key 2: modify last character18            while (sb.charAt(sb.length() - 1) < targetChar) {19                char newLastChar = (char) (sb.charAt(sb.length() - 1) + 1);20                sb.setCharAt(sb.length() - 1, newLastChar);21                result.add(sb.toString());22            }23        }24        return result;25    }26}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  List<String> stringSequence(String target) {4    List<String> ans = new ArrayList<>();5    for (char c : target.toCharArray()) {6      String s = ans.isEmpty() ? "" : ans.get(ans.size() - 1);7      for (char a = 'a'; a <= c; ++a) {8        String t = s + a;9        ans.add(t);10      }11    }12    return ans;13  }14}

1class Solution {2public:3  vector<string> stringSequence(string target) {4    vector<string> ans;5    for (char c : target) {6      string s = ans.empty() ? "" : ans.back();7      for (char a = 'a'; a <= c; ++a) {8        string t = s + a;9        ans.push_back(t);10      }11    }12    return ans;13  }14};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem