# Length of the Longest Alphabetical Continuous Substring
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/length-of-the-longest-alphabetical-continuous-substring)
Canonical: https://scaleengineer.com/dsa/problems/length-of-the-longest-alphabetical-continuous-substring
**Data structures:** String
---
## Problem
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.

# Approaches
## Brute-Force Approach
This approach involves checking every possible substring to see if it is an alphabetical continuous string. We iterate through all possible starting points of a substring and, for each starting point, we extend the substring as long as the alphabetical continuous property holds. We keep track of the maximum length found.
**Time:** O(n^2), where n is the length of the string `s`. The two nested loops lead to a quadratic runtime. In the worst-case scenario (a string like 'abcde...'), for each starting position `i`, the inner loop runs `n-i` times. · **Space:** O(1). We only use a constant amount of extra space for variables like `maxLength`, `currentLength`, and loop indices.
**Pros:** Simple to understand and implement.; It is a straightforward translation of the problem statement into code.
**Cons:** Highly inefficient for large inputs due to its O(n^2) time complexity.; Likely to cause a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.; Performs redundant computations. For example, in 'abcd', the check for 'bcd' is done independently after the check for 'abcd' has already processed those characters.
### Explanation
The brute-force method systematically explores all substrings. It uses two nested loops. The outer loop selects a starting character for a substring. The inner loop then expands this substring one character at a time, checking if the alphabetical continuity is maintained. A variable `currentLength` tracks the length of the valid continuous substring starting at the position defined by the outer loop. Whenever a character breaks the sequence, the inner loop terminates. The global `maxLength` is updated with the `currentLength` if it's larger. This process repeats for every character in the string as a potential starting point.

```java
class Solution {
    public int longestContinuousSubstring(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int maxLength = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            // For each starting point i, we find the longest
            // continuous substring starting from here.
            int currentLength = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(j) == s.charAt(j - 1) + 1) {
                    currentLength++;
                } else {
                    break;
                }
            }
            maxLength = Math.max(maxLength, currentLength);
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength` to 0. If the string is not empty, initialize it to 1.
- Iterate through the string with an index `i` from 0 to `n-1`, where `n` is the length of the string. This index `i` will be the starting point of a potential substring.
- For each `i`, start an inner loop with index `j` from `i + 1` to `n-1`.
- Inside the inner loop, check if the character at `j` is alphabetically consecutive to the character at `j-1` (i.e., `s.charAt(j) == s.charAt(j - 1) + 1`).
- If they are consecutive, it means the current alphabetical substring is extended. Increment a `currentLength` counter.
- If they are not consecutive, the sequence is broken. Break the inner loop.
- After the inner loop finishes for a given `i`, update `maxLength` with the maximum of its current value and the `currentLength` found for the substring starting at `i`.
- After the outer loop completes, return `maxLength`.

## Single Pass (Optimal) Approach
A more efficient solution can be achieved by iterating through the string just once. We can maintain a count of the current length of the alphabetical continuous substring. When the continuous sequence breaks, we update our overall maximum length and reset the current count.
**Time:** O(n), where n is the length of the string `s`. We perform a single pass through the string, and each operation inside the loop takes constant time. · **Space:** O(1). We only use a few variables (`maxLength`, `currentLength`, and the loop index) to store state, regardless of the input string's size.
**Pros:** Extremely efficient with a linear time complexity of O(n).; Optimal solution that passes for large constraints.; Uses constant extra space.; The logic is clean and easy to follow once the concept is understood.
**Cons:** May be slightly less intuitive for a beginner compared to the brute-force method, as it requires thinking about state (`currentLength`) that carries over through iterations.
### Explanation
This optimal approach uses a single pass over the string, which is a common technique for problems involving contiguous subarrays or substrings. We use a variable, `currentLength`, to track the length of the alphabetical continuous substring ending at the current position.

We iterate from the second character of the string. At each character, we check if it forms a continuous sequence with the preceding character. If `s.charAt(i)` is exactly one greater than `s.charAt(i-1)`, we are extending the current sequence, so we increment `currentLength`. If not, the sequence is broken, and we must start a new one from the current character, so we reset `currentLength` to 1.

In every step of the loop, we compare the `currentLength` with a `maxLength` variable and update `maxLength` if `currentLength` is greater. This ensures that `maxLength` always holds the length of the longest continuous substring found so far.

```java
class Solution {
    public int longestContinuousSubstring(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }

        int maxLength = 1;
        int currentLength = 1;

        for (int i = 1; i < s.length(); i++) {
            // Check if the current character is consecutive to the previous one
            if (s.charAt(i) == s.charAt(i - 1) + 1) {
                currentLength++;
            } else {
                // If the sequence is broken, reset the current length
                currentLength = 1;
            }
            // Update the maximum length found so far
            maxLength = Math.max(maxLength, currentLength);
        }

        return maxLength;
    }
}
```
### Algorithm
- Handle the edge case of a null or empty string by returning 0. Otherwise, any non-empty string has a longest continuous substring of at least length 1.
- Initialize `maxLength = 1` and `currentLength = 1`.
- Iterate through the string with an index `i` from 1 to `n-1` (where `n` is the string length).
- In each iteration, compare the character `s.charAt(i)` with the previous character `s.charAt(i-1)`.
- If `s.charAt(i) == s.charAt(i-1) + 1`, the alphabetical sequence continues. Increment `currentLength`.
- If the condition is false, the sequence is broken. Reset `currentLength` to 1, as the current character `s.charAt(i)` starts a new potential sequence.
- After either incrementing or resetting `currentLength`, update `maxLength = Math.max(maxLength, currentLength)` to keep track of the longest sequence found so far.
- After the loop finishes, return `maxLength`.

# Solutions
### Java

```java
class Solution { public int longestContinuousSubstring ( String s ) { int ans = 0 ; int i = 0 , j = 1 ; for (; j < s . length (); ++ j ) { ans = Math . max ( ans , j - i ); if ( s . charAt ( j ) - s . charAt ( j - 1 ) != 1 ) { i = j ; } } ans = Math . max ( ans , j - i ); return ans ; } }
```

### CPP

```cpp
class Solution { public: int longestContinuousSubstring ( string s ) { int ans = 0 ; int i = 0 , j = 1 ; for (; j < s . size (); ++ j ) { ans = max ( ans , j - i ); if ( s [ j ] - s [ j - 1 ] != 1 ) { i = j ; } } ans = max ( ans , j - i ); return ans ; } };
```

### Python

```python
class Solution : def longestContinuousSubstring ( self , s : str ) -> int : ans = 0 i , j = 0 , 1 while j < len ( s ): ans = max ( ans , j - i ) if ord ( s [ j ]) - ord ( s [ j - 1 ]) != 1 : i = j j += 1 ans = max ( ans , j - i ) return ans
```