Length of the Longest Alphabetical Continuous Substring Solution
Length of the Longest Alphabetical Continuous Substring solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Length of the Longest Alphabetical Continuous Substring is a medium coding problem on strings and sliding window, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Sliding Window
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An alphabetical continuous string is one whose letters are consecutive letters of the alphabet, in order — any substring of "abcdefghijklmnopqrstuvwxyz". For example "cde" qualifies, while "ace" and "za" do not (the alphabet does not wrap around).
Given a lowercase string s, return the length of its longest alphabetical continuous substring.
Example 1
Input: s = "xyzabcd"
Output: 4
Explanation: `"abcd"`. `"xyz"` has length 3, and `"za"` does not continue it.
Example 2
Input: s = "kairo"
Output: 1
Example 3
Input: s = "abcde"
Output: 5
Constraints
1 <= s.length <= 10^5s consists of only lowercase English letters
Hints for Length of the Longest Alphabetical Continuous Substring
Hint 1
A substring qualifies exactly when every letter is one more than the letter before it.
Hint 2
So the qualifying substrings are pieces of maximal runs where
s[i] == s[i-1] + 1.Hint 3
Scan once, extending the current run when the condition holds and restarting at 1 otherwise; track the longest run.
How to solve Length of the Longest Alphabetical Continuous Substring
The answer is the longest run of positions where each letter is exactly one more than the previous one; a single left-to-right scan measures every run.
Approach
- Set
cur = 1andbest = 1. - For
ifrom 1 ton - 1: ifs[i]is the letter right afters[i-1], increasecur; otherwise resetcur = 1. - After each step update
best = max(best, cur).
Why it works
Every alphabetical continuous substring lies inside a maximal run of the "next letter" relation, and every run is itself such a substring, so the longest one is the longest run. The scan visits each run once and cur is that run's length so far.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
'z'followed by'a'breaks a run — there is no wrap-around.- A run can be at most 26 letters long, but the scan does not need to rely on that.
- A single character always counts, so the answer is at least 1.
Reference solution
Python
def longestContinuousSubstring(s: str) -> int:
best = cur = 1
for i in range(1, len(s)):
if ord(s[i]) == ord(s[i - 1]) + 1:
cur += 1
else:
cur = 1
best = max(best, cur)
return bestJava
public static int longestContinuousSubstring(String s) {
int best = 1, cur = 1;
for (int i = 1; i < s.length(); i++) {
cur = s.charAt(i) == s.charAt(i - 1) + 1 ? cur + 1 : 1;
best = Math.max(best, cur);
}
return best;
}C++
int longestContinuousSubstring(string s) {
int best = 1, cur = 1;
for (size_t i = 1; i < s.size(); i++) {
cur = s[i] == s[i - 1] + 1 ? cur + 1 : 1;
best = max(best, cur);
}
return best;
}JavaScript
var longestContinuousSubstring = function(s) {
var best = 1, cur = 1;
for (var i = 1; i < s.length; i++) {
cur = s.charCodeAt(i) === s.charCodeAt(i - 1) + 1 ? cur + 1 : 1;
if (cur > best) best = cur;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Sliding Window Technique