algoadvance

Leetcode 467. Unique Substrings in Wraparound String

Problem Statement

We are given a string p which is assumed to be a substring of an infinite wraparound string of alphabet “abcdefghijklmnopqrstuvwxyz”. We need to determine the number of unique non-empty substrings of p that are present in this wraparound string.

Wraparound string means a string where “z” is followed by “a”, and it is infinite in both directions.

Example:
Input: p = "zab"
Output: 6
Explanation:
The substrings of p that are in the infinite wraparound string are: “z”, “a”, “b”, “za”, “ab”, and “zab”.

Clarifying Questions

1. Q: Can the string p contain duplicate characters? A: Yes, the string p can contain duplicated characters.

2. Q: Are there any constraints on the length of p? A: The problem does not explicitly mention constraints, but typically constraints for string lengths in such problems are manageable within typical limits (usually up to 10^4 or 10^5).

3. Q: What should be returned if the string p is empty? A: The problem specifies non-empty substrings, so for an empty input string, the result should be 0.

Strategy

1. Break Down the Problem:
   • Analyze how substrings in the wraparound string can be identified.
   • Each character in p can potentially start a valid series of substrings if it continues in the wraparound sequence.
2. Dynamic Programming Approach:
   • Use an array dp of size 26 representing each character of the alphabet.
   • For each character ch in p, maintain the maximum length of contiguous substring ending with ch that is in wraparound order.
   • Update the count of unique substrings ending at each character as we iterate through p.
3. Implementation Steps:
   • Initialize the dp array with zeros.
   • Traverse the string p character by character:
     • Calculate if the current character continues the wraparound sequence from the previous character.
     • Update the dp array with the maximum length of valid substrings found so far ending at current character.
   • Sum all values in the dp array to get the number of unique substrings.

Code

public class Solution {
    public int findSubstringInWraproundString(String p) {
        int[] dp = new int[26];
        int maxLen = 0;
        
        for (int i = 0; i < p.length(); i++) {
            if (i > 0 && (p.charAt(i) - p.charAt(i - 1) == 1 || p.charAt(i - 1) - p.charAt(i) == 25)) {
                maxLen++;
            } else {
                maxLen = 1;
            }
            int idx = p.charAt(i) - 'a';
            dp[idx] = Math.max(dp[idx], maxLen);
        }
        
        int result = 0;
        for (int count : dp) {
            result += count;
        }
        
        return result;
    }
}

Time Complexity

• Time Complexity: O(n) where n is the length of the string p. We make a single pass through the string p, and each character operation is O(1).
• Space Complexity: O(1). The space used is independent of the input size; the dp array has a fixed size of 26.

This strategy ensures that we efficiently count all unique substrings in the wraparound string specified.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?