Leetcode 2414: Length of the Longest Alphabetical Continuous Substring

Input: The input consists of a string 's'.

Example: s = "abcaz"

Constraints:

• 1 <= s.length <= 10^5

• s consists of only lowercase English letters

Output: Return the length of the longest continuous substring of consecutive letters in the alphabet.

Example: Output: 3

Constraints:

Goal: The goal is to find the longest substring of consecutive letters.

Steps:

• 1. Initialize a variable 'x' to track the current length of the substring.

• 2. Iterate over the string 's', checking if each character is consecutive to the previous one.

• 3. If the current character is consecutive, increment 'x'.

• 4. If the current character is not consecutive, reset 'x' to 1.

• 5. Keep track of the maximum value of 'x' during the iteration.

Goal: The solution must handle strings of length up to 100,000.

Steps:

• 1 <= s.length <= 10^5

• The input string contains only lowercase English letters.

Assumptions:

• The string 's' is not empty.

• The input will only contain lowercase English letters.

• Input: s = "abacada"

• Explanation: The longest continuous alphabetical substring is 'ab', which has a length of 2. The 'ac' and 'ad' substrings are not consecutive.

Approach: The approach is to iterate through the string and check for consecutive letters. If consecutive, increase the count. If not, reset and continue.

Observations:

• We need to check each character against the previous one to determine if they are consecutive.

• The solution needs to iterate through the string once, so the complexity should be linear.

• This problem can be solved efficiently in linear time, as we only need a single scan through the string.

Steps:

• 1. Initialize 'x' to 1 and 'ans' to 1.

• 2. Iterate through the string from the second character.

• 3. For each character, check if it is one greater than the previous character. If so, increase 'x'.

• 4. If the characters are not consecutive, reset 'x' to 1.

• 5. Update 'ans' with the maximum value of 'x'.

• 6. Return 'ans' as the result.

Empty Inputs:

• The input string will always have at least one character, as per the problem constraints.

Large Inputs:

• The solution must handle strings of length up to 100,000 efficiently.

Special Values:

• If the string contains only one character, the longest substring is the string itself with a length of 1.

Constraints:

• Ensure the solution runs in linear time due to the size constraints.

int longestContinuousSubstring(string s) {
    int x = 1, ans = 1;
    for(int i = 1; i < s.size(); i++) {
        if(s[i] == s[i -1] +1) {
            x++;
        } else x = 1;
        ans = max(x, ans);
    }
    return ans;
}

1 : Function Declaration

int longestContinuousSubstring(string s) {

Function declaration for 'longestContinuousSubstring'. It takes a string 's' as input.

2 : Variable Initialization

    int x = 1, ans = 1;

Initialize two variables: 'x' to track the length of the current continuous substring, and 'ans' to store the maximum length found.

3 : Loop Start

    for(int i = 1; i < s.size(); i++) {

Loop through the string starting from the second character, checking the relationship between consecutive characters.

4 : Condition Check

        if(s[i] == s[i -1] +1) {

Check if the current character 's[i]' is exactly 1 greater than the previous character 's[i - 1]'.

5 : Increment Counter

            x++;

If the condition is true, increment the length of the current continuous substring.

6 : Reset Counter

        } else x = 1;

If the condition is false, reset the length of the current continuous substring to 1.

7 : Update Maximum

        ans = max(x, ans);

Update the maximum length found so far between the current substring length 'x' and the stored maximum 'ans'.

8 : Return Statement

    return ans;

Return the maximum length of the continuous substring found.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is linear because we only need to traverse the string once.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is constant as we only need a few integer variables.

Leetcode 2414: Length of the Longest Alphabetical Continuous Substring

Explore →