Length of the Longest Alphabetical Continuous Substring

Medium
1240.

Length of the Longest Alphabetical Continuous Substring

Length of the Longest Alphabetical Continuous Substring is a medium coding problem on strings and sliding window, asked in Amazon and Google interviews.

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^5
  • s consists of only lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var longestContinuousSubstring = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • s consists of only lowercase English letters

Hints for Length of the Longest Alphabetical Continuous Substring

  1. Hint 1

    A substring qualifies exactly when every letter is one more than the letter before it.

  2. Hint 2

    So the qualifying substrings are pieces of maximal runs where s[i] == s[i-1] + 1.

  3. 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

  1. Set cur = 1 and best = 1.
  2. For i from 1 to n - 1: if s[i] is the letter right after s[i-1], increase cur; otherwise reset cur = 1.
  3. 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 best

Java

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