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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Sequence of Strings Appeared on the Screen

Number: 3566

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Alice types a given target string on a computer that has a special keyboard with only two keys. Key 1 appends the character "a" to the current string, and Key 2 changes the last character of the string to its next character in the alphabet (with "z" wrapping around to "a"). Starting with an empty string and using only legal presses (initially only Key 1 since the screen is empty), determine and return the list of all strings that appear on the screen while typing target with the minimum number of key presses.

Key Insights

  • The initial operation is always to press Key 1 since the screen starts empty.
  • For the first character of target, start with "a" and then use Key 2 repeatedly until the displayed character equals target[0].
  • For every subsequent character in target, first press Key 1 to append an "a" to the current string, then repeatedly press Key 2 to increment the newly appended "a" until it becomes the desired character.
  • The operations for each character are independent. Each appended letter starts at "a" and is incremented to the target letter.
  • This greedy strategy guarantees the minimum key presses because it only performs the exact number of increments required.

Space and Time Complexity

Time Complexity: O(n * 26) in the worst case, where n is the length of target (each appended "a" may need up to 25 increments).
Space Complexity: O(n * m), where m is the average length of the strings in the sequence (since intermediate strings are stored in the output list).

Solution

The approach simulates the key presses one by one.

  1. Start with an empty string and build the result list.
  2. For the first target letter, press Key 1 to start with "a" and then repeatedly press Key 2 until the letter becomes target[0].
  3. For each subsequent letter in the target string:
    • Append an "a" using Key 1.
    • Use Key 2 to increment the last character until it matches the corresponding character in target.
  4. Each operation (Key 1 and Key 2) is simulated by updating the current string and adding the new string to the result list. The key data structures used are a list (or array) to collect the sequence of strings and basic string manipulation. The solution leverages a straightforward simulation strategy that is both simple and effective.

Code Solutions

# Python solution with comments showing the logic step-by-step.

def find_sequence(target: str) -> list:
    result = []                # List to store all intermediate strings.
    current = ""               # Starting with an empty string.
    
    # Build the string one character at a time.
    for index, target_char in enumerate(target):
        # Key 1: Append 'a' to start the new character entry.
        current += 'a'
        result.append(current) # Add the string after pressing key 1.
        
        # Increment the last character using key2 until it matches target_char.
        # Only if the current letter is not already equal to target_char.
        while current[-1] != target_char:
            # Get the last character and calculate its next character.
            last_char = current[-1]
            # Compute next character with wrap-around.
            next_char = 'a' if last_char == 'z' else chr(ord(last_char) + 1)
            # Update the last character of the string.
            current = current[:-1] + next_char
            # Append the updated string to the result list.
            result.append(current)
    
    return result

# Example usage:
target = "abc"
print(find_sequence(target))
← Back to All Questions