Jobs

Interviews

Discussions

Length of the Longest Alphabetical Continuous Substring

Medium

Asked by:

35 views

Topics:

Strings

An alphabetical continuous string is a string consisting of consecutive letters in the alphabet. In other words, it is any substring of the string "abcdefghijklmnopqrstuvwxyz".

For example, "abc" is an alphabetical continuous string, while "acb" and "za" are not.

Given a string s consisting of lowercase letters only, return the length of the longest alphabetical continuous substring.

Example 1:

Input: s = "abacaba"
Output: 2
Explanation: There are 4 distinct continuous substrings: "a", "b", "c" and "ab".
"ab" is the longest continuous substring.

Example 2:

Input: s = "abcde"
Output: 5
Explanation: "abcde" is the longest continuous substring.

Constraints:

1 <= s.length <= 10⁵
s consists of only English lowercase letters.

Try coding it in LeetCode

Length of the Longest Alphabetical Continuous Substring

Medium

Asked by:

35 views

Topics:

Strings

An alphabetical continuous string is a string consisting of consecutive letters in the alphabet. In other words, it is any substring of the string "abcdefghijklmnopqrstuvwxyz".

For example, "abc" is an alphabetical continuous string, while "acb" and "za" are not.

Given a string s consisting of lowercase letters only, return the length of the longest alphabetical continuous substring.

Example 1:

Input: s = "abacaba"
Output: 2
Explanation: There are 4 distinct continuous substrings: "a", "b", "c" and "ab".
"ab" is the longest continuous substring.

Example 2:

Input: s = "abcde"
Output: 5
Explanation: "abcde" is the longest continuous substring.

Constraints:

1 <= s.length <= 10⁵
s consists of only English lowercase letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input string guaranteed to be ASCII, or could it contain Unicode characters?
What should be returned if the input string is empty or null?
Is the comparison case-sensitive? Should 'a' be considered adjacent to 'b', but 'A' not?
If there are multiple longest alphabetical continuous substrings of the same length, should I return just any one of them, or is there a specific one I should prioritize (e.g., the first occurrence)?
Can the input string contain spaces or other non-alphabetic characters, and how should those characters be handled?

Brute Force Solution

Approach

The brute force method for finding the longest alphabetical sequence involves checking every possible group of letters within the text. It's like examining every slice of the text to see if it forms an alphabetical sequence and then picking the longest one found.

Here's how the algorithm would work step-by-step:

Start by looking at the first letter of the text and seeing if it starts an alphabetical sequence.
Then, consider the first two letters, then the first three, and so on, checking each group to see if the letters are in alphabetical order.
Repeat this process, but starting from the second letter in the text, then the third, and so on, each time checking if the group of letters is in alphabetical order.
As you check each group, remember the longest alphabetical sequence you've found so far.
Once you've checked every possible group of letters, the longest sequence you remembered is the answer.

Code Implementation

def find_longest_alphabetical_sequence(text):
    longest_sequence_length = 0

    for starting_index in range(len(text)): # Check all possible starting positions

        for ending_index in range(starting_index, len(text)): # Expands substring to the right
            substring = text[starting_index : ending_index+1]

            is_alphabetical = True
            for char_index in range(len(substring) - 1): # Ensures no out-of-bounds error

                # Verify characters are in alphabetical order
                if substring[char_index] > substring[char_index + 1]:
                    is_alphabetical = False
                    break

            # We've identified a valid alphabetical substring
            if is_alphabetical:

                # Update the longest length if needed
                substring_length = len(substring)
                if substring_length > longest_sequence_length:
                    longest_sequence_length = substring_length

    return longest_sequence_length

Big(O) Analysis

Time Complexity

O(n³) – The outer loop iterates through each of the n characters in the string as a potential starting point for a substring. The inner loop then checks substrings of increasing length starting from that position, up to the end of the string, which requires up to n iterations. For each substring, we need to verify if it's in alphabetical order, requiring another iteration of at most n comparisons. Therefore, the total number of operations is proportional to n * n * n, which simplifies to O(n³).

Space Complexity

O(1) – The brute force approach described iterates through substrings of the input string but does not use any auxiliary data structures that scale with the input size N (the length of the string). It maintains a variable to store the length of the longest alphabetical sequence found so far, but this is constant space. No temporary lists, hash maps, or recursion are used. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The goal is to find the longest part of a string where the letters are in order, like 'abc' or 'ghijkl'. We can solve this efficiently by walking through the string just once, keeping track of the current alphabetical streak and updating the longest one we've seen so far.

Here's how the algorithm would work step-by-step:

Start at the beginning of the string.
Consider the first letter as the start of a potential alphabetical streak.
Look at the next letter. If it comes right after the previous letter in the alphabet, then the streak continues, so include it.
If the next letter doesn't follow the alphabet, the alphabetical streak ends there.
Keep track of the length of each streak you find.
Compare the length of each streak to the longest streak you've seen so far and update the longest one if needed.
Continue moving through the entire string, finding and comparing the lengths of each alphabetical streak.
Once you've reached the end of the string, the longest streak you've kept track of is the answer.

Code Implementation

def longest_alphabetical_continuous_substring(input_string):
    string_length = len(input_string)
    if string_length == 0:
        return 0

    longest_substring_length = 1
    current_substring_length = 1

    for i in range(1, string_length):
        # Check if the current character continues the alphabetical sequence.
        if ord(input_string[i]) == ord(input_string[i - 1]) + 1:

            current_substring_length += 1

            # Update the longest substring length if needed.
            if current_substring_length > longest_substring_length:
                longest_substring_length = current_substring_length

        else:
            # Reset the current substring length as the sequence is broken.
            current_substring_length = 1

    return longest_substring_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n exactly once. During this single pass, each character is examined to determine if it extends the current alphabetical substring. The comparisons within the loop are constant time operations. Therefore, the runtime complexity is directly proportional to the length of the input string, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm keeps track of the current streak length and the longest streak length seen so far. These variables, such as current length and max length, require constant space regardless of the input string's length N. No auxiliary data structures that scale with the input string's size are created. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 immediately since an empty string has no substring.
String with a single character	Return 1 as a single character is a continuous substring of length 1.
String with all identical characters (e.g., 'aaaa')	Return 1 as the longest alphabetical substring can only be of length 1.
String with characters in reverse alphabetical order (e.g., 'zyxw')	Return 1 as the longest alphabetical substring can only be of length 1.
String with non-alphabetic characters (e.g., 'ab!cd')	Ignore non-alphabetic characters or remove them before processing; or return 0 if the cleaned string is empty.
String with mixed case characters (e.g., 'aBcD')	Convert the entire string to lowercase or uppercase before processing to ensure consistent comparisons.
String approaching maximum allowed length	Ensure the solution has O(n) time complexity to handle very long strings efficiently without timeouts or excessive memory usage.
String with only two characters that are not consecutive	Return 1 because the longest substring must have consecutive alphabetical letters, which is not possible.

Null or empty input string

How to Handle:

Return 0 immediately since an empty string has no substring.

String with a single character

How to Handle:

Return 1 as a single character is a continuous substring of length 1.

String with all identical characters (e.g., 'aaaa')

How to Handle:

Return 1 as the longest alphabetical substring can only be of length 1.

String with characters in reverse alphabetical order (e.g., 'zyxw')

How to Handle:

Return 1 as the longest alphabetical substring can only be of length 1.

String with non-alphabetic characters (e.g., 'ab!cd')

How to Handle:

Ignore non-alphabetic characters or remove them before processing; or return 0 if the cleaned string is empty.

String with mixed case characters (e.g., 'aBcD')

How to Handle:

Convert the entire string to lowercase or uppercase before processing to ensure consistent comparisons.

String approaching maximum allowed length

How to Handle:

Ensure the solution has O(n) time complexity to handle very long strings efficiently without timeouts or excessive memory usage.

String with only two characters that are not consecutive

How to Handle:

Return 1 because the longest substring must have consecutive alphabetical letters, which is not possible.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input string guaranteed to be ASCII, or could it contain Unicode characters?
What should be returned if the input string is empty or null?
Is the comparison case-sensitive? Should 'a' be considered adjacent to 'b', but 'A' not?
If there are multiple longest alphabetical continuous substrings of the same length, should I return just any one of them, or is there a specific one I should prioritize (e.g., the first occurrence)?
Can the input string contain spaces or other non-alphabetic characters, and how should those characters be handled?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the first letter of the text and seeing if it starts an alphabetical sequence.
Then, consider the first two letters, then the first three, and so on, checking each group to see if the letters are in alphabetical order.
Repeat this process, but starting from the second letter in the text, then the third, and so on, each time checking if the group of letters is in alphabetical order.
As you check each group, remember the longest alphabetical sequence you've found so far.
Once you've checked every possible group of letters, the longest sequence you remembered is the answer.

Code Implementation

def find_longest_alphabetical_sequence(text):
    longest_sequence_length = 0

    for starting_index in range(len(text)): # Check all possible starting positions

        for ending_index in range(starting_index, len(text)): # Expands substring to the right
            substring = text[starting_index : ending_index+1]

            is_alphabetical = True
            for char_index in range(len(substring) - 1): # Ensures no out-of-bounds error

                # Verify characters are in alphabetical order
                if substring[char_index] > substring[char_index + 1]:
                    is_alphabetical = False
                    break

            # We've identified a valid alphabetical substring
            if is_alphabetical:

                # Update the longest length if needed
                substring_length = len(substring)
                if substring_length > longest_sequence_length:
                    longest_sequence_length = substring_length

    return longest_sequence_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the beginning of the string.
Consider the first letter as the start of a potential alphabetical streak.
Look at the next letter. If it comes right after the previous letter in the alphabet, then the streak continues, so include it.
If the next letter doesn't follow the alphabet, the alphabetical streak ends there.
Keep track of the length of each streak you find.
Compare the length of each streak to the longest streak you've seen so far and update the longest one if needed.
Continue moving through the entire string, finding and comparing the lengths of each alphabetical streak.
Once you've reached the end of the string, the longest streak you've kept track of is the answer.

Code Implementation

def longest_alphabetical_continuous_substring(input_string):
    string_length = len(input_string)
    if string_length == 0:
        return 0

    longest_substring_length = 1
    current_substring_length = 1

    for i in range(1, string_length):
        # Check if the current character continues the alphabetical sequence.
        if ord(input_string[i]) == ord(input_string[i - 1]) + 1:

            current_substring_length += 1

            # Update the longest substring length if needed.
            if current_substring_length > longest_substring_length:
                longest_substring_length = current_substring_length

        else:
            # Reset the current substring length as the sequence is broken.
            current_substring_length = 1

    return longest_substring_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 immediately since an empty string has no substring.
String with a single character	Return 1 as a single character is a continuous substring of length 1.
String with all identical characters (e.g., 'aaaa')	Return 1 as the longest alphabetical substring can only be of length 1.
String with characters in reverse alphabetical order (e.g., 'zyxw')	Return 1 as the longest alphabetical substring can only be of length 1.
String with non-alphabetic characters (e.g., 'ab!cd')	Ignore non-alphabetic characters or remove them before processing; or return 0 if the cleaned string is empty.
String with mixed case characters (e.g., 'aBcD')	Convert the entire string to lowercase or uppercase before processing to ensure consistent comparisons.
String approaching maximum allowed length	Ensure the solution has O(n) time complexity to handle very long strings efficiently without timeouts or excessive memory usage.
String with only two characters that are not consecutive	Return 1 because the longest substring must have consecutive alphabetical letters, which is not possible.

Null or empty input string

How to Handle:

Return 0 immediately since an empty string has no substring.

String with a single character

How to Handle:

Return 1 as a single character is a continuous substring of length 1.

String with all identical characters (e.g., 'aaaa')

How to Handle:

Return 1 as the longest alphabetical substring can only be of length 1.

String with characters in reverse alphabetical order (e.g., 'zyxw')

How to Handle:

Return 1 as the longest alphabetical substring can only be of length 1.

String with non-alphabetic characters (e.g., 'ab!cd')

How to Handle:

Ignore non-alphabetic characters or remove them before processing; or return 0 if the cleaned string is empty.

String with mixed case characters (e.g., 'aBcD')

How to Handle:

Convert the entire string to lowercase or uppercase before processing to ensure consistent comparisons.

String approaching maximum allowed length

How to Handle:

Ensure the solution has O(n) time complexity to handle very long strings efficiently without timeouts or excessive memory usage.

String with only two characters that are not consecutive

How to Handle:

Return 1 because the longest substring must have consecutive alphabetical letters, which is not possible.