Find the Sequence of Strings Appeared on the Screen
MedPrompt
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 <= 400targetconsists 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
targetCharof the inputtargetstring. - For each
targetChar: a. Simulate pressing Key 1: Append 'a' tocurrentStringusing string concatenation (currentString = currentString + "a"). b. Add the newcurrentStringto theresultlist. c. Simulate pressing Key 2: Start with the last character as 'a'. While it is less thantargetChar, increment the character and updatecurrentString. 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 theresultlist. - After iterating through all characters of
target, return theresultlist.
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.
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; }}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.
Solutions
Solution
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; }}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.