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 thelongest alphabetical continuous substring.

Examples

Example 1

1
2
3
4

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

1
2
3

Input: s = "abcde"
Output: 5
Explanation: "abcde" is the longest continuous substring.

Constraints

  • 1 <= s.length <= 10^5
  • s consists of only English lowercase letters.

Solution

Method 1 – Sliding Window

Intuition

We want the longest substring where each character is the next letter in the alphabet compared to the previous one. We can scan the string and keep track of the current window of consecutive letters.

Approach

  1. Initialize ans and cur to 1.
  2. Iterate through the string from the second character:
    • If the current character is the next letter after the previous, increment cur.
    • Otherwise, reset cur to 1.
    • Update ans with the maximum of ans and cur.
  3. Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int longestContinuousSubstring(string s) {
        int ans = 1, cur = 1;
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == s[i-1] + 1) cur++;
            else cur = 1;
            ans = max(ans, cur);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func longestContinuousSubstring(s string) int {
    ans, cur := 1, 1
    for i := 1; i < len(s); i++ {
        if s[i] == s[i-1]+1 {
            cur++
        } else {
            cur = 1
        }
        if cur > ans { ans = cur }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int longestContinuousSubstring(String s) {
        int ans = 1, cur = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i-1) + 1) cur++;
            else cur = 1;
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun longestContinuousSubstring(s: String): Int {
        var ans = 1; var cur = 1
        for (i in 1 until s.length) {
            if (s[i] == s[i-1]+1) cur++
            else cur = 1
            ans = maxOf(ans, cur)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def longestContinuousSubstring(self, s: str) -> int:
        ans = cur = 1
        for i in range(1, len(s)):
            if ord(s[i]) == ord(s[i-1]) + 1:
                cur += 1
            else:
                cur = 1
            ans = max(ans, cur)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn longest_continuous_substring(s: String) -> i32 {
        let s = s.as_bytes();
        let mut ans = 1;
        let mut cur = 1;
        for i in 1..s.len() {
            if s[i] == s[i-1] + 1 {
                cur += 1;
            } else {
                cur = 1;
            }
            ans = ans.max(cur);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    longestContinuousSubstring(s: string): number {
        let ans = 1, cur = 1;
        for (let i = 1; i < s.length; i++) {
            if (s.charCodeAt(i) === s.charCodeAt(i-1) + 1) cur++;
            else cur = 1;
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s. We scan the string once.
  • 🧺 Space complexity: O(1), only a few variables are used.