Length of the Longest Alphabetical Continuous Substring

MEDIUM

Description

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

Approaches

Checkout 2 different approaches to solve Length of the Longest Alphabetical Continuous Substring. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(1). We only use a constant amount of extra space for variables like `maxLength`, `currentLength`, and loop indices.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Length of the Longest Alphabetical Continuous Substring. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Length of the Longest Alphabetical Continuous Substring

Data Structures:

String