DEV Community

Cover image for 2981. Find Longest Special Substring That Occurs Thrice I
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

1

2981. Find Longest Special Substring That Occurs Thrice I

2981. Find Longest Special Substring That Occurs Thrice I

Difficulty: Medium

Topics: Hash Table, String, Binary Search, Sliding Window, Counting

You are given a string s that consists of lowercase English letters.

A string is called special if it is made up of only a single character. For example, the string "abc" is not special, whereas the strings "ddd", "zz", and "f" are special.

Return the length of the longest special substring of s which occurs at least thrice, or -1 if no special substring occurs at least thrice.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

  • Input: s = "aaaa"
  • Output: 2
  • Explanation: The longest special substring which occurs thrice is "aa": substrings "aaaa", "aaaa", and "aaaa".
    • It can be shown that the maximum length achievable is 2.

Example 2:

  • Input: s = "abcdef"
  • Output: -1
  • Explanation: There exists no special substring which occurs at least thrice. Hence return -1.

Example 3:

  • Input: s = "abcdef"
  • Output: 1
  • Explanation: The longest special substring which occurs thrice is "a": substrings "abcaba", "abcaba", and "abcaba".
    • It can be shown that the maximum length achievable is 1.

Constraints:

  • 3 <= s.length <= 50
  • s consists of only lowercase English letters.

Hint:

  1. The constraints are small.
  2. Brute force checking all substrings.

Solution:

We can use a brute force approach due to the small constraints of s (length of up to 50). We'll:

  1. Iterate over possible lengths of substrings (from longest to shortest).
  2. Check all substrings of the given length and count their occurrences.
  3. If a substring occurs at least three times, check if it is special (made of one repeated character).
  4. Return the length of the longest such substring. If no substring satisfies the conditions, return -1.

Let's implement this solution in PHP: 2981. Find Longest Special Substring That Occurs Thrice I

<?php
/**
 * @param String $s
 * @return Integer
 */
function maximumLength($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to check if a substring is special
 *
 * @param $substring
 * @return bool
 */
function isSpecial($substring) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maximumLength("aaaa") . "\n"; // Output: 2
echo maximumLength("abcdef") . "\n"; // Output: -1
echo maximumLength("abcabcabc") . "\n"; // Output: 1
?>
Enter fullscreen mode Exit fullscreen mode

Explanation:

  1. Outer Loop: We iterate over the possible lengths of substrings, starting with the longest. This ensures we return the longest special substring as soon as we find it.
  2. Sliding Window: For each substring length, we use a sliding window approach to extract all substrings of that length.
  3. Counting Substrings: We use an associative array ($countMap) to store and count occurrences of each substring.
  4. Checking Special: A helper function isSpecial checks if the substring is made up of only one repeated character.
  5. Returning the Result: If a valid substring is found, we return its length; otherwise, we return -1.

Complexity

  • Time Complexity: O(n3) in the worst case because we:
    1. Iterate over n substring lengths.
    2. Extract O(n) substrings for each length.
    3. Check if each substring is special, which takes O(n) time.
  • Space Complexity: O(n2) due to the substring counting map.

This brute force approach is feasible given the constraints (n <= 50).

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

πŸ‘‹ While you are here

Reinvent your career. Join DEV.

It takes one minute and is worth it for your career.

Get started

Top comments (0)

Heroku

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site

πŸ‘‹ Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay