Find the Sequence of Strings Appeared on the Screen solution and explanation
5 more videos on this problem
Find the Sequence of Strings Appeared on the Screen || LeetCode Weekly Contest 420codi · 0:45 · 1K views
Leetcode Weekly Contest 420 | 3324. Find the Sequence of Strings Appeared on the Screen | CodeFodCodeFod · 9:09 · 349 views
Leetcode Weekly Contest 420 || Q1. Find the Sequence of Strings Appeared on the ScreenExpertFunda · 4:07 · 241 views
3324. Find the Sequence of Strings Appeared on the Screen (Leetcode Medium)Programming Live with Larry · 6:46 · 198 views
Find the Sequence of Strings Appeared on the Screen | LeetcodeEthos Typos · 10:56 · 104 views
Find the Sequence of Strings Appeared on the ScreenNeetCoders · 4:09 · 41 views
The 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 <= 400targetconsists only of lowercase English letters.
Approach overview
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.
Approach 1: Iterative String Construction
This approach involves simulating each key press step by step. Begin with an empty string and use Key 1 to add characters or Key 2 to change the last character until the target is achieved.
Iteratively compare each target character with the current screen character to decide whether to append or modify with Key 2.
def find_sequence(target):
result = []
current = "a"
result.append(current)
for i in range(1, len(target) + 1):
while len(current) < i:
current += 'a'
result.append(current)
while current[i - 1] != target[i - 1]:
current = current[:i-1] + chr((ord(current[i - 1]) - ord('a') + 1) % 26 + ord('a')) + current[i:]
result.append(current)
return result
target = "abc"
output = find_sequence(target)
for s in output:
print(s)import java.util.ArrayList;
import java.util.List;
public class Main {
public static List<String> findSequence(String target) {
List<String> result = new ArrayList<>();
StringBuilder current = new StringBuilder("a");
result.add(current.toString());
int n = target.length();
for (int i = 1; i <= n; i++) {
while (current.length() < i) {
current.append('a');
result.add(current.toString());
}
while (current.charAt(i - 1) != target.charAt(i - 1)) {
current.setCharAt(i - 1, current.charAt(i - 1) == 'z' ? 'a' : (char)(current.charAt(i - 1) + 1));
result.add(current.toString());
}
}
return result;
}
public static void main(String[] args) {
String target = "abc";
List<String> result = findSequence(target);
for (String s : result) {
System.out.println(s);
}
}
}#include <iostream>
#include <vector>
using namespace std;
vector<string> findSequence(string target) {
vector<string> result;
string current = "a";
result.push_back(current);
int n = target.length();
for (int i = 1; i <= n; ++i) {
while (current.length() < i) {
current += 'a';
result.push_back(current);
}
while (current[i - 1] != target[i - 1]) {
current[i - 1] = current[i - 1] == 'z' ? 'a' : current[i - 1] + 1;
result.push_back(current);
}
}
return result;
}
int main() {
string target = "abc";
vector<string> result = findSequence(target);
for (const string& s : result) {
cout << s << endl;
}
return 0;
}function findSequence(target) {
let result = [];
let current = "a";
result.push(current);
for (let i = 1; i <= target.length; i++) {
while (current.length < i) {
current += 'a';
result.push(current);
}
while (current[i - 1] !== target[i - 1]) {
let chars = current.split('');
chars[i - 1] = chars[i - 1] === 'z' ? 'a' : String.fromCharCode(chars[i - 1].charCodeAt(0) + 1);
current = chars.join('');
result.push(current);
}
}
return result;
}
const target = "abc";
console.log(findSequence(target));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void findSequence(char* target, char** result, int* returnSize) {
int n = strlen(target);
*returnSize = 0;
result[*returnSize] = malloc(n + 1);
strcpy(result[*returnSize], "a");
(*returnSize)++;
char current[n + 1];
strcpy(current, "a");
for (int i = 1; i <= n; ++i) {
while (strlen(current) < i) {
current[strlen(current)] = 'a';
current[strlen(current) + 1] = '\0';
result[*returnSize] = malloc(strlen(current) + 1);
strcpy(result[*returnSize], current);
(*returnSize)++;
}
while (current[i - 1] != target[i - 1]) {
current[i - 1] = current[i - 1] == 'z' ? 'a' : current[i - 1] + 1;
result[*returnSize] = malloc(strlen(current) + 1);
strcpy(result[*returnSize], current);
(*returnSize)++;
}
}
}
int main() {
char* target = "abc";
char* result[1000];
int returnSize;
findSequence(target, result, &returnSize);
for(int i = 0; i < returnSize; i++) {
printf("%s\n", result[i]);
free(result[i]);
}
return 0;
}using System;
using System.Collections.Generic;
class Program {
static List<string> FindSequence(string target) {
List<string> result = new List<string>();
string current = "a";
result.Add(current);
for (int i = 1; i <= target.Length; i++) {
while (current.Length < i) {
current += 'a';
result.Add(current);
}
char[] chars = current.ToCharArray();
while (chars[i - 1] != target[i - 1]) {
chars[i - 1] = chars[i - 1] == 'z' ? 'a' : (char)(chars[i - 1] + 1);
current = new string(chars);
result.Add(current);
}
}
return result;
}
static void Main() {
string target = "abc";
List<string> output = FindSequence(target);
output.ForEach(Console.WriteLine);
}
}Python simplifies string handling with slicing and character manipulation through ASCII arithmetic.
We construct the sequence similarly via stepwise changes.
Time Complexity: O(n * 26).
Space Complexity: O(n^2) due to the sequence storage.
Approach 2: Optimized Approach with Direct Character Manipulation
An optimized approach focuses on noticing that each time Key 1 is used, it adds 'a', and any further changes with Key 2 depends on the target character. Thus, compute the difference directly and assemble the sequence more directly without individually adding each character.
def find_sequence_optimized(target):
result = []
current = "a"
result.append(current)
for i in range(1, len(target) + 1):
diff = ord(target[i - 1]) - ord('a')
while len(current) < i:
current += 'a'
result.append(current)
for _ in range(diff):
current = current[:i-1] + chr((ord(current[i - 1]) - ord('a') + 1) % 26 + ord('a')) + current[i:]
result.append(current)
return result
target = "abc"
output = find_sequence_optimized(target)
for s in output:
print(s)import java.util.ArrayList;
import java.util.List;
public class Main {
public static List<String> findSequenceOptimized(String target) {
List<String> result = new ArrayList<>();
StringBuilder current = new StringBuilder("a");
result.add(current.toString());
int n = target.length();
for (int i = 1; i <= n; i++) {
int diff = target.charAt(i - 1) - 'a';
while (current.length() < i) {
current.append('a');
result.add(current.toString());
}
for (int j = 0; j < diff; j++) {
current.setCharAt(i - 1, current.charAt(i - 1) == 'z' ? 'a' : (char)(current.charAt(i - 1) + 1));
result.add(current.toString());
}
}
return result;
}
public static void main(String[] args) {
String target = "abc";
List<String> result = findSequenceOptimized(target);
for (String s : result) {
System.out.println(s);
}
}
}#include <iostream>
#include <vector>
using namespace std;
vector<string> findSequenceOptimized(string target) {
vector<string> result;
string current = "a";
result.push_back(current);
int n = target.length();
for (int i = 1; i <= n; ++i) {
int diff = target[i-1] - 'a';
while (current.length() < i) {
current += 'a';
result.push_back(current);
}
for (int j = 0; j < diff; ++j) {
current[i - 1] = current[i - 1] == 'z' ? 'a' : current[i - 1] + 1;
result.push_back(current);
}
}
return result;
}
int main() {
string target = "abc";
vector<string> result = findSequenceOptimized(target);
for (const string& s : result) {
cout << s << endl;
}
return 0;
}function findSequenceOptimized(target) {
let result = [];
let current = "a";
result.push(current);
for (let i = 1; i <= target.length; i++) {
let diff = target.charCodeAt(i - 1) - 'a'.charCodeAt(0);
while (current.length < i) {
current += 'a';
result.push(current);
}
for (let j = 0; j < diff; j++) {
let chars = current.split('');
chars[i - 1] = chars[i - 1] === 'z' ? 'a' : String.fromCharCode(chars[i - 1].charCodeAt(0) + 1);
current = chars.join('');
result.push(current);
}
}
return result;
}
const target = "abc";
console.log(findSequenceOptimized(target));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void findSequenceOptimized(char* target, char** result, int* returnSize) {
int n = strlen(target);
*returnSize = 0;
result[*returnSize] = malloc(n + 1);
strcpy(result[*returnSize], "a");
(*returnSize)++;
char current[n + 1];
strcpy(current, "a");
for (int i = 1; i <= n; ++i) {
int diff = (target[i-1] - 'a');
while (strlen(current) < i) {
current[strlen(current)] = 'a';
current[strlen(current) + 1] = '\0';
result[*returnSize] = malloc(strlen(current) + 1);
strcpy(result[*returnSize], current);
(*returnSize)++;
}
for (int j = 0; j < diff; ++j) {
current[i - 1] = current[i - 1] == 'z' ? 'a' : current[i - 1] + 1;
result[*returnSize] = malloc(strlen(current) + 1);
strcpy(result[*returnSize], current);
(*returnSize)++;
}
}
}
int main() {
char* target = "abc";
char* result[1000];
int returnSize;
findSequenceOptimized(target, result, &returnSize);
for(int i = 0; i < returnSize; i++) {
printf("%s\n", result[i]);
free(result[i]);
}
return 0;
}using System;
using System.Collections.Generic;
class Program {
static List<string> FindSequenceOptimized(string target) {
List<string> result = new List<string>();
string current = "a";
result.Add(current);
for (int i = 1; i <= target.Length; i++) {
int diff = target[i - 1] - 'a';
while (current.Length < i) {
current += 'a';
result.Add(current);
}
char[] chars = current.ToCharArray();
for (int j = 0; j < diff; j++) {
chars[i - 1] = chars[i - 1] == 'z' ? 'a' : (char)(chars[i - 1] + 1);
current = new string(chars);
result.Add(current);
}
}
return result;
}
static void Main() {
string target = "abc";
List<string> output = FindSequenceOptimized(target);
output.ForEach(Console.WriteLine);
}
}Python also leverages character arithmetic directly to minimize the need for iteration in transformations.
Time Complexity: O(n).
Space Complexity: O(n^2).
Approach 3: Simulation
We can simulate Alice's typing process, starting from an empty string and updating the string after each keystroke until the target string is obtained.
The time complexity is O(n^2 times |\Sigma|), where n is the length of the target string and \Sigma is the character set, which in this case is the set of lowercase letters, so |\Sigma| = 26.
function stringSequence(target: string): string[] {
const ans: string[] = [];
for (const c of target) {
let s = ans.length > 0 ? ans[ans.length - 1] : '';
for (let a = 'a'.charCodeAt(0); a <= c.charCodeAt(0); a++) {
const t = s + String.fromCharCode(a);
ans.push(t);
}
}
return ans;
}func stringSequence(target string) (ans []string) {
for _, c := range target {
s := ""
if len(ans) > 0 {
s = ans[len(ans)-1]
}
for a := 'a'; a <= c; a++ {
t := s + string(a)
ans = append(ans, t)
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative String Construction | Time Complexity: Space Complexity: |
| Optimized Approach with Direct Character Manipulation | Time Complexity: Space Complexity: |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative String Construction | O(26 * n) ≈ O(n) | O(n) | Best for clarity and interview explanations where direct simulation is expected |
| Direct Character Manipulation (Array Based) | O(26 * n) ≈ O(n) | O(n) | When optimizing string updates in languages with immutable strings |
Frequently asked questions
Is Find the Sequence of Strings Appeared on the Screen easy or hard?
The problem is generally rated Medium because it requires careful simulation and tracking of intermediate states. The algorithm itself is straightforward, but missing small steps in the process can lead to incorrect sequences.
Find the Sequence of Strings Appeared on the Screen Python/Java solution
In Python or Java, maintain a current string (or character array) and simulate the operations. Increment the last character until it equals the target character, storing each intermediate result, then append 'a' when moving to the next index. Both implementations run in O(n) effective time and O(n) space.
How to solve Find the Sequence of Strings Appeared on the Screen in O(n)?
Simulate the screen operations using a current string or character array. For each target character, repeatedly increment the last character until it matches the target, recording every intermediate state. Then append 'a' to start constructing the next position. Because each character increases at most 25 times, the total runtime is linear in the target length.
What is the best approach for Find the Sequence of Strings Appeared on the Screen?
The best approach is direct simulation of the typing process. Start with the string "a", increment the last character until it matches the target character, and append 'a' when moving to the next position. This approach runs in O(26 * n) time, effectively O(n), and uses O(n) space for storing the sequence of intermediate strings.
Is Find the Sequence of Strings Appeared on the Screen asked at Google/Amazon/Meta?
This style of problem appears in interviews at companies like Amazon, Google, and Meta when testing simulation and string manipulation skills. While the exact problem may vary, candidates are often asked to model a process step-by-step and track intermediate states efficiently.
What data structure is used in Find the Sequence of Strings Appeared on the Screen?
The core data structures are a string or a mutable character array to represent the current screen content, and a list or array to store all intermediate strings. The algorithm mainly relies on string manipulation and simple iteration.
What is the time complexity of Find the Sequence of Strings Appeared on the Screen?
The time complexity is O(26 * n), where n is the length of the target string. Each position may require up to 25 increments to reach the desired character from 'a'. Since 26 is a constant alphabet size, the complexity simplifies to O(n). Space complexity is O(n) for storing the resulting sequence of strings.