mediumStringsPattern: Fundamentals
Identifying Pattern Substrings Solution
Problem Statement
Given a string and a pattern, find the length of the longest substring that occurs at least twice in the string and also contains the given pattern as a substring.
Examples
Example 1:
Input:string = 'abcabcabc', pattern = 'abc'
Output:3
Explanation: The longest substring that occurs at least twice in the string 'abcabcabc' and also contains the pattern 'abc' is 'abc' itself with a length of 3.
Example 2:
Input:string = 'abababab', pattern = 'aba'
Output:3
Explanation: The longest substring that occurs at least twice in the string 'abababab' and also contains the pattern 'aba' is 'aba' itself with a length of 3.
Constraints
- The length of the input string is at most 1000 characters.
- The length of the pattern is at least 1 character and at most 100 characters.
- The input string and pattern only contain lowercase English letters.
Time: O(n^2) Space: O(n)
The optimal approach involves using a hashmap to store the frequency of each substring and a sliding window to generate substrings, reducing the time complexity to O(n^2).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.