algoadvance

Leetcode 467. Unique Substrings in Wraparound String

Problem Statement

Consider a string “p” where “p” is a substring of the infinite wraparound string of “abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz…”. We need to find out how many unique non-empty substrings of “p” are present in this infinite wraparound string.

Clarifying Questions

  1. Can “p” contain any characters other than lowercase English alphabets?
    • No, “p” consists of only lowercase English alphabets.
  2. What is the maximum length of the string “p”?
    • The length of “p” can be up to 100,000.
  3. Should the substrings be contiguous in “p”?
    • Yes, substrings are contiguous segments of “p”.

Strategy

  1. Define a dp array (length 26) such that dp[i] represents the length of the longest substring ending with the character i + 'a' in the string “p” which forms a contiguous substring in the wraparound alphabet.

  2. Iterate through the string “p”:
    • For each character, check if it extends a previous contiguous substring (for example, ‘c’ following ‘b’).
    • Update the dp array value for the character if the new length is greater than the existing value.
  3. Add up values in the dp array to get the total count of unique substrings.

Code

Here’s the implementation of the described strategy:

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int findSubstringInWraproundString(string p) {
    vector<int> dp(26, 0);  // dp[i] means the maximum unique substring end with 'a' + i

    int n = p.length();
    int maxLengthCur = 0;  // max length of the current valid substring

    for (int i = 0; i < n; ++i) {
        if (i > 0 && (p[i] - p[i-1] == 1 || p[i-1] - p[i] == 25)) {
            // current character is following last character in the wrapround string
            maxLengthCur++;
        } else {
            maxLengthCur = 1;
        }
        int index = p[i] - 'a';
        dp[index] = max(dp[index], maxLengthCur);
    }

    // Sum up all counts in dp array
    int result = 0;
    for (int count : dp) {
        result += count;
    }

    return result;
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string “p”. This is because we only make a single pass through the string and perform constant-time operations for each character. The space complexity is O(1) since the dp array size is fixed at 26.

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