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

Length of the Longest Alphabetical Continuous Substring

Number: 2492

Difficulty: Medium

Paid? No

Companies: Amazon, TikTok

Problem Description

Given a string s consisting only of lowercase letters, find the length of the longest alphabetical continuous substring. An alphabetical continuous substring is a substring in which every subsequent character is the next letter in the English alphabet. For example, "abc" is valid, whereas "acb" or "za" are not.

Key Insights

  • Iterate through the string while comparing each character with its previous character.
  • If the current character is exactly one more than the previous (using their ASCII or ordinal representation), then it continues an alphabetical sequence.
  • Reset the count when the sequence is broken.
  • Keep track of the maximum sequence length encountered.
  • The solution uses a single pass through the string, ensuring O(n) time complexity.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The approach involves iterating over the given string and maintaining a count of the current valid alphabetical sequence. For each character, we check if its ASCII value is exactly one more than that of its predecessor. If yes, we increase the current count. If not, we reset the count to 1. During the iteration, we update the result with the maximum count seen so far. This utilizes a simple linear scan and some constant extra space, making it both time and space efficient.

Code Solutions

# Define the function to find the longest alphabetical continuous substring
def longest_alphabetical_continuous_substring(s):
    # Initialize the maximum length and current sequence length
    max_length = 1
    current_length = 1

    # Loop through the string starting from the second character
    for i in range(1, len(s)):
        # Check if current character is consecutive in alphabetical order relative to the previous character
        if ord(s[i]) - ord(s[i-1]) == 1:
            current_length += 1  # Increase current length if in sequence
        else:
            current_length = 1  # Reset current length if sequence breaks
        # Update maximum length if needed
        max_length = max(max_length, current_length)
    
    return max_length

# Example usage:
s = "abacaba"
print(longest_alphabetical_continuous_substring(s))  # Output: 2
← Back to All Questions