Frontend School

Longest Compliant Substring

DSA
medium

Longest Compliant Substring

Medium
String
Sliding Window
Hash Map

Overview

In ServiceNow's configuration management systems, ensuring data compliance is critical. Imagine you're tasked with developing a utility that identifies portions of configuration strings that strictly adhere to a predefined compliance profile. This involves not only checking for the presence of required characters but also ensuring that no unauthorized characters are included.

What you need to do / Task

Implement a function longestCompliantSubstring that takes two string inputs: configStr (the configuration string to analyze) and profileStr (the compliance profile). Your function should find the longest substring within configStr that satisfies the following two conditions:

  1. Character Inclusion: The substring must contain all unique characters present in profileStr at least once.
  2. Character Exclusivity: The substring must contain only characters that are present in profileStr. No other characters from configStr are allowed within the compliant substring.

If no such compliant substring exists, the function should return 0.

Input & output

Function Signature: function longestCompliantSubstring(configStr: string, profileStr: string): number

  • configStr: The string representing the configuration data. 1 <= configStr.length <= 10^5.
  • profileStr: The string representing the compliance profile. 1 <= profileStr.length <= 52 (representing lowercase and uppercase English letters).

Return Value:

  • An integer representing the length of the longest compliant substring found. Return 0 if no such substring exists.

Clarifications

  • Case Sensitivity: Character comparisons are case-sensitive. 'a' is different from 'A'.
  • Empty profileStr: The problem constraints guarantee profileStr.length >= 1.
  • Character Set: Assume configStr and profileStr will only contain English letters (a-z, A-Z).

Examples

1

Example 1

Input:

configStr = "abracadabraXabc", profileStr = "abc"

Output:

3

Note:

The longest compliant substring is "abc" itself (at the end). 'X' in "abracadabraXabc" prevents longer substrings from being compliant. Other substrings like "abr" contain 'r' which is not in profileStr.

2

Example 2

Input:

configStr = "bacacb", profileStr = "abc"

Output:

6

Note:

The entire configStr "bacacb" is compliant. It contains 'a', 'b', 'c' and no other characters.

3

Example 3

Input:

configStr = "axbyc", profileStr = "abc"

Output:

0

Note:

No substring of configStr can be compliant because 'x' and 'y' are not in profileStr, violating the exclusivity condition for any substring containing them.

4

Example 4

Input:

configStr = "zzzaaabcc", profileStr = "za"

Output:

6

Note:

The substring "zzzaaa" at index 0 to 5 is compliant. It contains 'z' and 'a' and no other characters. Its length is 6. While "zaaa" (index 2-5) is also compliant, it is shorter.

Constraints

Constraints & assumptions

  • 1 <= configStr.length <= 10^5
  • 1 <= profileStr.length <= 52 (representing unique lowercase and uppercase English letters)
  • configStr and profileStr consist of English letters only (a-z, A-Z).
  • The solution should aim for optimal time and space complexity.

What interviewers evaluate

  • Correctness: The solution accurately identifies the longest compliant substring under all specified conditions and edge cases.
  • Algorithm Efficiency: Optimal time complexity, typically O(N + P) where N is configStr.length and P is profileStr.length.
  • Edge Case Handling: Correct behavior for inputs where no compliant substring exists, or when profileStr has only one unique character.
  • Code Quality: Readability, maintainability, and proper use of data structures.

Loading editor...