3458. Select K Disjoint Special Substrings LeetCode Solution

In this guide, you will get 3458. Select K Disjoint Special Substrings LeetCode Solution with the best time and space complexity. The solution to Select K Disjoint Special Substrings 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.

Problem Statement
Complexity Analysis
Select K Disjoint Special Substrings solution in C++
Select K Disjoint Special Substrings solution in Java
Select K Disjoint Special Substrings solution in Python
Additional Resources

3458. Select K Disjoint Special Substrings LeetCode Solution image

Problem Statement of Select K Disjoint Special Substrings

Given a string s of length n and an integer k, determine whether it is possible to select k disjoint special substrings.
A special substring is a substring where:

Any character present inside the substring should not appear outside it in the string.
The substring is not the entire string s.

Note that all k substrings must be disjoint, meaning they cannot overlap.
Return true if it is possible to select k such disjoint special substrings; otherwise, return false.

Example 1:

Input: s = “abcdbaefab”, k = 2
Output: true
Explanation:

We can select two disjoint special substrings: “cd” and “ef”.
“cd” contains the characters ‘c’ and ‘d’, which do not appear elsewhere in s.
“ef” contains the characters ‘e’ and ‘f’, which do not appear elsewhere in s.

Example 2:

Input: s = “cdefdc”, k = 3
Output: false
Explanation:
There can be at most 2 disjoint special substrings: “e” and “f”. Since k = 3, the output is false.

Example 3:

Input: s = “abeabe”, k = 0
Output: true

Constraints:

2 <= n == s.length <= 5 * 104
0 <= k <= 26
s consists only of lowercase English letters.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(26) = O(1)

3458. Select K Disjoint Special Substrings LeetCode Solution in C++

class Solution {
 public:
  bool maxSubstringLength(string s, int k) {
    const int n = s.length();
    vector<int> first(26, n);
    vector<int> last(26, -1);
    vector<char> seenOrder;
    // dp[i] := the maximum disjoint special substrings for the first i letters
    vector<int> dp(n + 1);

    for (int i = 0; i < n; ++i) {
      const char c = s[i];
      const int a = c - 'a';
      if (first[a] == n) {
        first[a] = i;
        seenOrder.push_back(c);
      }
      last[a] = i;
    }

    for (const char c : seenOrder) {
      const int a = c - 'a';
      for (int j = first[a]; j < last[a]; ++j) {
        const int b = s[j] - 'a';
        first[a] = min(first[a], first[b]);
        last[a] = max(last[a], last[b]);
      }
    }

    for (int i = 0; i < n; ++i) {
      const char c = s[i];
      const int a = c - 'a';
      if (last[a] != i || (first[a] == 0 && i == n - 1))
        dp[i + 1] = dp[i];
      else  // Start a new special substring.
        dp[i + 1] = max(dp[i], 1 + dp[first[a]]);
    }

    return dp[n] >= k;
  }
};
/* code provided by PROGIEZ */

3458. Select K Disjoint Special Substrings LeetCode Solution in Java

class Solution {
  public boolean maxSubstringLength(String s, int k) {
    final int n = s.length();
    int[] first = new int[26];
    int[] last = new int[26];
    // dp[i] := the maximum disjoint special substrings for the first i letters
    int[] dp = new int[n + 1];
    List<Character> seenOrder = new ArrayList<>();

    Arrays.fill(first, n);
    Arrays.fill(last, -1);

    for (int i = 0; i < n; ++i) {
      final char c = s.charAt(i);
      final int a = c - 'a';
      if (first[a] == n) {
        first[a] = i;
        seenOrder.add(c);
      }
      last[a] = i;
    }

    for (final char c : seenOrder) {
      final int a = c - 'a';
      for (int j = first[a]; j < last[a]; ++j) {
        final int b = s.charAt(j) - 'a';
        first[a] = Math.min(first[a], first[b]);
        last[a] = Math.max(last[a], last[b]);
      }
    }

    for (int i = 0; i < n; i++) {
      final char c = s.charAt(i);
      final int a = c - 'a';
      if (last[a] != i || (first[a] == 0 && i == n - 1))
        dp[i + 1] = dp[i];
      else // Start a new special substring.
        dp[i + 1] = Math.max(dp[i], 1 + dp[first[a]]);
    }

    return dp[n] >= k;
  }
}
// code provided by PROGIEZ

3458. Select K Disjoint Special Substrings LeetCode Solution in Python

class Solution:
  def maxSubstringLength(self, s: str, k: int) -> bool:
    n = len(s)
    first = [n] * 26
    last = [-1] * 26
    # dp[i] := the maximum disjoint special substrings for the first i letters
    dp = [0] * (n + 1)
    seenOrder = []

    for i, c in enumerate(s):
      a = ord(c) - ord('a')
      if first[a] == n:
        first[a] = i
        seenOrder.append(c)
      last[a] = i

    for c in seenOrder:
      a = ord(c) - ord('a')
      for j in range(first[a], last[a]):
        b = ord(s[j]) - ord('a')
        first[a] = min(first[a], first[b])
        last[a] = max(last[a], last[b])

    for i, c in enumerate(s):
      a = ord(c) - ord('a')
      if last[a] != i or (first[a] == 0 and i == n - 1):
        dp[i + 1] = dp[i]
      else:  # Start a new special substring.
        dp[i + 1] = max(dp[i], 1 + dp[first[a]])

    return dp[n] >= k
 # code by PROGIEZ