Find the Sequence of Strings Appeared on the Screen

Find the Sequence of Strings Appeared on the Screen - Problem

String Simulation Medium

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

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.

Input & Output

Example 1 — Basic Case

$ Input: target = "abc"

› Output: ["a","ab","aba","abb","abc"]

💡 Note: Start empty → add 'a' → add 'a' to get 'aa' then cycle to 'ab' → add 'a' to get 'aba', cycle to 'abb', then 'abc'

Example 2 — Single Character

$ Input: target = "a"

› Output: ["a"]

💡 Note: Only need to add 'a' once, no cycling required

Example 3 — Cycling Required

$ Input: target = "za"

› Output: ["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","za"]

💡 Note: First position cycles through entire alphabet to reach 'z', then add 'a'

Constraints

1 ≤ target.length ≤ 1000
target consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

Target string 'bc' to be typed

Process

Use Key 1 (add 'a') and Key 2 (cycle alphabet) to build string

Output

All intermediate strings in order

Key Takeaway

🎯 Key Insight: Simulate the exact typing process by extending with 'a' then cycling to target character

Asked in

G Google 23 M Microsoft 15

The key insight is to simulate Alice's typing process exactly: for each target character, first add 'a' to extend the string length, then cycle through the alphabet until reaching the desired character. Best approach is direct simulation. Time: O(n × k), Space: O(n × m)

Common Approaches

Approach	Time	Space	Notes
✓ Direct Simulation	O(n × k)	O(n × m)	Simulate the exact typing process character by character

Direct Simulation — Algorithm Steps

Start with empty string
For each target character: add 'a' then cycle to target
Record all intermediate strings

Visualization

Tap to expand

Step-by-Step Walkthrough

Add 'a'

Press Key 1 to add 'a' at new position

Cycle Letters

Press Key 2 repeatedly to reach target character

Record Steps

Save all intermediate strings to result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char** solution(char* target, int* returnSize) {
    int targetLen = strlen(target);
    int maxResults = targetLen * 27; // worst case: each char needs 26 cycles + 1 add
    char** result = (char**)malloc(maxResults * sizeof(char*));
    *returnSize = 0;
    
    char current[1001] = "";
    int currentLen = 0;
    
    for (int i = 0; i < targetLen; i++) {
        // Add 'a' to extend string length
        current[currentLen] = 'a';
        currentLen++;
        current[currentLen] = '\0';
        
        result[*returnSize] = (char*)malloc((currentLen + 1) * sizeof(char));
        strcpy(result[*returnSize], current);
        (*returnSize)++;
        
        // Cycle through alphabet until we reach target character
        while (current[currentLen - 1] != target[i]) {
            char lastChar = current[currentLen - 1];
            char nextChar = (lastChar == 'z') ? 'a' : (char)(lastChar + 1);
            current[currentLen - 1] = nextChar;
            
            result[*returnSize] = (char*)malloc((currentLen + 1) * sizeof(char));
            strcpy(result[*returnSize], current);
            (*returnSize)++;
        }
    }
    
    return result;
}

int main() {
    char target[1001];
    fgets(target, sizeof(target), stdin);
    target[strcspn(target, "\n")] = 0; // Remove newline
    
    int returnSize;
    char** result = solution(target, &returnSize);
    
    // Format output as JSON array
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
        free(result[i]);
    }
    printf("]\n");
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k)

n characters in target, each requiring up to k=26 alphabet cycles

✓ Linear Growth

Space Complexity

O(n × m)

Storing all intermediate strings, where m is average string length

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~15 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Direct Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler