Skip to main content
Talentd

Length of the Longest Alphabetical Continuous Substring - Solution & Explanation

MediumString18 min readAsked at: Amazon, IBM, Tiktok
Practice this problem

Problem Statement

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 <= 105
  • s consists of only English lowercase letters.

Approach Overview

Problem Overview: You are given a lowercase string s. The task is to find the length of the longest substring where every character is exactly one letter after the previous one in the alphabet. For example, "abc" or "xyz" are valid because each character follows its predecessor by +1 in ASCII order.

Approach 1: Sliding Window (O(n) time, O(1) space)

This approach scans the string once while maintaining the length of the current alphabetical run. Start from the second character and compare it with the previous one. If s[i] - s[i-1] == 1, the sequence continues and you extend the window by increasing the current length. Otherwise, reset the window length to 1 because the alphabetical chain breaks. Track the maximum length seen during the traversal. The algorithm uses constant extra memory and performs a single linear pass, which makes it optimal. This technique is a classic pattern from sliding window problems and appears frequently in string traversal tasks.

Approach 2: Dynamic Programming (O(n) time, O(n) space)

The dynamic programming formulation treats each index as the end of a potential alphabetical substring. Define dp[i] as the length of the longest valid substring ending at index i. If s[i] - s[i-1] == 1, extend the previous result with dp[i] = dp[i-1] + 1. Otherwise start a new sequence with dp[i] = 1. After processing the entire string, the maximum value in the DP array is the answer. This mirrors the logic used in dynamic programming problems where each state depends on the previous one. While it is conceptually clear, it uses extra memory compared to the sliding window solution.

Recommended for interviews: The sliding window solution is what most interviewers expect. It demonstrates that you can recognize consecutive relationships and maintain a running window in O(n) time with O(1) space. Implementing the DP version first can help reason about the recurrence, but reducing it to a constant-space scan shows stronger algorithmic optimization skills.

Approach 1: Sliding Window Approach

The sliding window approach will help us identify the longest substring of consecutive characters. We iterate through the string, expanding the window by adding characters as long as they are consecutive. If characters are not consecutive, we reset the start of the window to the current character. We maintain a variable to track the maximum length found during this process.

This implementation uses a loop to iterate through the string and checks the difference between consecutive characters. When characters are consecutive, it increases the current length. If a break is found, it resets the current length to 1. The maximum length is updated whenever a longer continuous substring is found.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), since only a few constant space variables are used.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

This approach uses an array to keep track of the longest continuous substring ending with each character of the input string. We initialize an array with ones. As we iterate through the string, we increment the array value if the current character forms a continuous sequence with the previous character, and we keep track of the maximum value in this array.

In this C implementation, an array dp stores the length of the longest substring ending at each character position, and updates the dp values by checking for sequential characters and tracking maximum length found.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), due to the additional array used for dynamic programming.

Try this approach in the editor →

Approach 3: Single Pass

We can traverse the string s and use a variable ans to record the length of the longest lexicographically consecutive substring, and another variable cnt to record the length of the current consecutive substring. Initially, ans = cnt = 1.

Next, we start traversing the string s from the character at index 1. For each character s[i], if s[i] - s[i - 1] = 1, it means the current character and the previous character are consecutive. In this case, cnt = cnt + 1, and we update ans = max(ans, cnt). Otherwise, it means the current character and the previous character are not consecutive, so cnt = 1.

Finally, we return ans.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Approach

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), since only a few constant space variables are used.

Dynamic Programming Approach

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), due to the additional array used for dynamic programming.

Single Pass—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding WindowO(n)O(1)Best general solution. One pass with constant memory. Preferred for interviews.
Dynamic ProgrammingO(n)O(n)Useful when explaining recurrence relations or when extending the problem to store intermediate states.

Video Solution

2414. Length of the Longest Alphabetical Continuous Substring | Leetcode Weekly 311 | LeetCode 2414 • Bro Coders • 971 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Length of the Longest Alphabetical Continuous Substring easy or hard?
The problem is generally considered medium difficulty. The core logic is simple once you notice the consecutive ASCII relationship, but recognizing the sliding window pattern quickly during an interview can be slightly tricky.
Length of the Longest Alphabetical Continuous Substring Python/Java solution
Python and Java implementations both follow the same logic: iterate through the string and check if consecutive characters differ by exactly one in ASCII value. Maintain a running length and update the maximum result. The algorithm runs in O(n) time and uses O(1) extra space.
How to solve Length of the Longest Alphabetical Continuous Substring in O(n)?
Iterate through the string while tracking the current consecutive alphabetical length. If s[i] - s[i-1] equals 1, increase the current length; otherwise reset it to 1. Keep updating a global maximum during the scan. This single-pass strategy achieves O(n) time and constant memory.
What is the best approach for Length of the Longest Alphabetical Continuous Substring?
The sliding window approach is the best solution. Traverse the string once and check if the difference between consecutive characters is exactly 1. If it is, extend the current window; otherwise reset it. This runs in O(n) time with O(1) space and is the standard interview solution.
Is Length of the Longest Alphabetical Continuous Substring asked at Google/Amazon/Meta?
Variants of consecutive character or substring scanning problems appear in interviews at companies like Amazon and Google. The pattern tests your ability to process strings efficiently using linear scans, sliding window logic, and ASCII character comparisons.
What data structure is used in Length of the Longest Alphabetical Continuous Substring?
The problem mainly relies on string traversal rather than complex data structures. The optimal solution uses simple counters with a sliding window pattern. A dynamic programming array can also be used to store the longest valid substring ending at each index.
What is the time complexity of Length of the Longest Alphabetical Continuous Substring?
The optimal algorithm runs in O(n) time because the string is scanned exactly once. Each character is compared with its previous neighbor to check if the alphabetical sequence continues. Space complexity can be O(1) using a sliding window or O(n) with a dynamic programming array.

Ready to solve this problem?

Practice Length of the Longest Alphabetical Continuous Substring with our built-in code editor and test cases.

Practice on FleetCode
Previous

Arithmetic Slices

Next

Longest Consecutive Sequence