Leetcode 467: Unique Substrings in Wraparound String
grid47 Exploring patterns and algorithms
Sep 21, 2024
5 min read
Solution to LeetCode 467: Unique Substrings in Wraparound String Problem
Given a string s, return the number of unique non-empty substrings of s that are present in the infinite wraparound string ‘abcdefghijklmnopqrstuvwxyz’.
Problem
Approach
Steps
Complexity
Input: The input consists of a string `s`.
Example: s = 'c'
Constraints:
• 1 <= s.length <= 10^5
• s consists of lowercase English letters.
Output: Return the number of unique substrings of `s` that are found in the infinite wraparound string.
Example: Output: 1
Constraints:
• The output should be an integer representing the count of unique substrings in the wraparound base string.
Goal: The goal is to find all unique substrings of `s` and check if they exist in the infinite wraparound string.
Steps:
• 1. Traverse the string `s` and find substrings that are contiguous in the wraparound base string.
• 2. Track the maximum length of continuous substrings from `s` that can be matched to substrings in the base string.
• 3. Count the number of unique substrings by leveraging the tracked maximum lengths.
Goal: The string's length can be as large as 10^5, so the solution needs to be efficient.
Steps:
• Handle strings with lengths up to 10^5.
• The string consists only of lowercase English letters.
Assumptions:
• The input string `s` is non-empty and contains only lowercase letters.
• Input: s = 'c'
• Explanation: The substring 'c' is present in the infinite base string.
• Input: s = 'db'
• Explanation: The substrings 'd' and 'b' are both present in the infinite base string.
• Input: s = 'zab'
• Explanation: The substrings 'z', 'a', 'b', 'za', 'ab', and 'zab' are all present in the infinite base string.
Approach: We solve the problem by finding the substrings of `s` that can be matched in the infinite wraparound string.
Observations:
• The problem involves identifying substrings that are continuous in the base string, which requires recognizing circular sequences.
• A key observation is that substrings can be tracked by looking at the maximum length of valid sequences from `s` that match the base string.
Steps:
• 1. Initialize an array to keep track of the length of the longest contiguous substring ending at each character in `s`.
• 2. Iterate over the string and check if each character continues a valid substring in the base string, updating the length as needed.
• 3. Sum the lengths of unique valid substrings and return the result.
Empty Inputs:
• An empty string is not allowed as per the constraints.
Large Inputs:
• Ensure the solution handles large inputs efficiently, with lengths up to 10^5.
Special Values:
• Consider cases where the string contains repeating characters or sequences, such as 'aaaa'.
Constraints:
• The solution must run in linear time to handle large inputs.
intfindSubstringInWraproundString(string p) {
vector<int> len(26, 0);
int cur =1;
len[p[0] -'a'] =1;
for(int i =1; i < p.size(); i++) {
if((p[i] +26- p[i -1]) %26==1) cur++;
else cur =1;
len[p[i] -'a'] = max(len[p[i] -'a'], cur);
}
return accumulate(len.begin(), len.end(), 0);
}
1 : Function Definition
intfindSubstringInWraproundString(string p) {
Defines the function `findSubstringInWraproundString` that takes a string `p` and returns the total count of unique substrings that can be formed in a wraparound string.
2 : Vector Initialization
vector<int> len(26, 0);
Initializes a vector `len` of size 26 to store the maximum length of substrings ending with each letter of the alphabet, initialized to 0.
3 : Variable Initialization
int cur =1;
Initializes the variable `cur` to 1, which keeps track of the current length of the ongoing sequence of consecutive characters in the alphabet.
4 : First Character Handling
len[p[0] -'a'] =1;
Sets the length of the substring ending with the first character of `p` (indexed by `p[0] - 'a'`) to 1, as it forms a single-character substring.
5 : Loop Start
for(int i =1; i < p.size(); i++) {
Begins a loop to iterate through the string `p`, starting from the second character, to check for continuous character sequences.
6 : Sequence Check
if((p[i] +26- p[i -1]) %26==1) cur++;
Checks if the current character `p[i]` and the previous character `p[i-1]` are consecutive in the alphabet, considering wraparound behavior. If they are consecutive, it increments `cur`.
7 : Sequence Reset
else cur =1;
If the current character is not consecutive to the previous one, it resets `cur` to 1, starting a new sequence.
8 : Update Lengths
len[p[i] -'a'] = max(len[p[i] -'a'], cur);
Updates the maximum length of the substring ending with the character `p[i]` by comparing the current value in `len` and the ongoing sequence length `cur`.
9 : Final Calculation
returnaccumulate(len.begin(), len.end(), 0);
Calculates the sum of all the maximum lengths of substrings ending with each letter of the alphabet using the `accumulate` function, returning the total number of unique substrings.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) since we process each character of the string once.
Best Case: O(26)
Worst Case: O(26)
Description: The space complexity is O(26) due to the fixed array used to track the maximum lengths of substrings for each character.
