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".
"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 <= 105s consists of only English lowercase letters.The sliding window approach will help us identify the longest substring of consecutive characters. We iterate through the string, expanding the window by adding characters as long as they are consecutive. If characters are not consecutive, we reset the start of the window to the current character. We maintain a variable to track the maximum length found during this process.
This implementation uses a loop to iterate through the string and checks the difference between consecutive characters. When characters are consecutive, it increases the current length. If a break is found, it resets the current length to 1. The maximum length is updated whenever a longer continuous substring is found.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), since only a few constant space variables are used.
This approach uses an array to keep track of the longest continuous substring ending with each character of the input string. We initialize an array with ones. As we iterate through the string, we increment the array value if the current character forms a continuous sequence with the previous character, and we keep track of the maximum value in this array.
In this C implementation, an array dp stores the length of the longest substring ending at each character position, and updates the dp values by checking for sequential characters and tracking maximum length found.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), due to the additional array used for dynamic programming.
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n), where n is the length of the string. |
| Dynamic Programming Approach | Time Complexity: O(n), where n is the length of the string. |
Longest Substring Without Repeating Characters - Leetcode 3 - Python • NeetCode • 657,697 views views
Watch 9 more video solutions →Practice Length of the Longest Alphabetical Continuous Substring with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor