467. Unique Substrings in Wraparound String LeetCode Solution

In this guide, you will get 467. Unique Substrings in Wraparound String LeetCode Solution with the best time and space complexity. The solution to Unique Substrings in Wraparound String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Unique Substrings in Wraparound String solution in C++
4. Unique Substrings in Wraparound String solution in Java
5. Unique Substrings in Wraparound String solution in Python
6. Additional Resources

Problem Statement of Unique Substrings in Wraparound String

We define the string base to be the infinite wraparound string of “abcdefghijklmnopqrstuvwxyz”, so base will look like this:

“…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd….”.

Given a string s, return the number of unique non-empty substrings of s are present in base.

Example 1:

Input: s = “a”
Output: 1
Explanation: Only the substring “a” of s is in base.

Example 2:

Input: s = “cac”
Output: 2
Explanation: There are two substrings (“a”, “c”) of s in base.

Example 3:

Input: s = “zab”
Output: 6
Explanation: There are six substrings (“z”, “a”, “b”, “za”, “ab”, and “zab”) of s in base.

Constraints:

1 <= s.length <= 105
s consists of lowercase English letters.

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(26)

467. Unique Substrings in Wraparound String LeetCode Solution in C++

class Solution {
 public:
  int findSubstringInWraproundString(string p) {
    int maxLength = 1;
    // count[i] := the number of substrings ending in ('a' + i)
    vector<int> count(26);

    for (int i = 0; i < p.length(); ++i) {
      if (i > 0 && (p[i] - p[i - 1] == 1 || p[i - 1] - p[i] == 25))
        ++maxLength;
      else
        maxLength = 1;
      const int index = p[i] - 'a';
      count[index] = max(count[index], maxLength);
    }

    return accumulate(count.begin(), count.end(), 0);
  }
};
/* code provided by PROGIEZ */

467. Unique Substrings in Wraparound String LeetCode Solution in Java

class Solution {
  public int findSubstringInWraproundString(String p) {
    int maxLength = 1;
    // count[i] := the number of substrings ending in ('a' + i)
    int[] count = new int[26];

    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))
        ++maxLength;
      else
        maxLength = 1;
      final int index = p.charAt(i) - 'a';
      count[index] = Math.max(count[index], maxLength);
    }

    return Arrays.stream(count).sum();
  }
}
// code provided by PROGIEZ

467. Unique Substrings in Wraparound String LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.