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

Lexicographically Smallest String After Substring Operation

Number: 2828

Difficulty: Medium

Paid? No

Companies: Goldman Sachs, IBM, Agoda

Problem Description

Given a string s of lowercase English letters, you are allowed to perform exactly one operation: choose any non-empty substring of s and replace every letter in that substring with its preceding letter in the alphabet (with 'a' wrapping around to 'z'). The goal is to obtain the lexicographically smallest string possible after performing this operation.

Key Insights

  • Only one contiguous substring can be selected for transformation.
  • To achieve the lexicographically smallest result, you want to decrease letters as early as possible in the string.
  • Start from the beginning of the string and look for the first character that is not 'a'; then, continue decrementing subsequent characters (until you hit an 'a' again) in that same contiguous block.
  • If the entire string consists of only 'a's, then the only option is to convert the last letter into a 'z' (due to wrap-around).

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(n), primarily to store the modified string (or O(1) if converting in-place on a mutable array).

Solution

The solution involves scanning the string from the left until a character that is not 'a' is found. Once found, enter a loop to decrement each consecutive character by one (using wrap-around for 'a' to 'z'). The moment you reach a character that is 'a' (or you finish the substring), break out of the loop. If no character was found (i.e., the string consisted of all 'a's), simply change the last character to 'z'.

Data structures used are:

  • An array (or char array) representation of the string for easy in-place modification.
  • Basic loop constructs to iterate over the string characters.

This greedy strategy ensures that the changes are applied as early as possible, yielding the lexicographically smallest result.

Code Solutions

def smallestString(s):
    s_list = list(s)  # Convert string to list for in-place modification
    n = len(s_list)
    changed = False
    # Find the first character that isn't 'a'
    for i in range(n):
        if s_list[i] != 'a':
            # Process the contiguous substring until an 'a' is encountered
            while i < n and s_list[i] != 'a':
                # Decrement the character (with wrap-around for 'a')
                s_list[i] = chr((ord(s_list[i]) - ord('a') - 1) % 26 + ord('a'))
                i += 1
            changed = True
            break
    # If no change occurred (string consists of all 'a's), change the last letter to 'z'
    if not changed:
        s_list[-1] = 'z'
    return "".join(s_list)

# Example usage:
print(smallestString("cbabc"))  # Expected Output: "baabc"
← Back to All Questions