Scale Engineer

Length of the Longest Alphabetical Continuous Substring

Med
#2198Time: 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.
Data structures
String

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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.

Trade-offs

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.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem