We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Sequence of Strings Appeared on the Screen

Difficulty: Medium

Problem Description

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, and Key 2 changes the last character of the string on the screen to its next character in the English alphabet. 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.

Key Insights

  • Alice starts with an empty string and can only press key 1 initially.
  • Pressing key 1 adds an "a", and pressing key 2 changes the last character to the next character in the alphabet.
  • The goal is to generate all possible strings leading up to the target string in the most efficient manner.

Space and Time Complexity

Time Complexity: O(n^2), where n is the length of the target string. This accounts for generating all possible strings and the character transformations. Space Complexity: O(n), where n is the length of the target string. This is used for storing the resulting list of strings.

Solution

To solve this problem, we can utilize a breadth-first search (BFS) approach, starting from an empty string. We will maintain a queue to explore all possible strings by pressing key 1 and key 2. The algorithm will append "a" to the current string and also explore changing the last character to its next character in the alphabet. We will continue this process until we have generated all strings leading up to the target string, ensuring we do not revisit strings we have already generated.

Code Solutions

def findSequence(target: str) -> List[str]:
    from collections import deque
    
    result = []
    queue = deque([''])  # Start with an empty string
    
    while queue:
        current = queue.popleft()
        
        # Only add the current string if it is not empty
        if current:
            result.append(current)
        
        # Press Key 1: Add 'a' to the current string
        next_string = current + 'a'
        if next_string <= target:
            queue.append(next_string)
        
        # Press Key 2: Change the last character if possible
        if current:
            last_char = current[-1]
            if last_char < 'z':
                next_char = chr(ord(last_char) + 1)
            else:
                next_char = 'a'
            next_string = current[:-1] + next_char  # Change the last character
            if next_string <= target:
                queue.append(next_string)
    
    return result
← Back to All Questions