Maximum Repeating Substring

🏠 ⬅️ ➡️

For a string sequence, a string word is k-repeating if word concatenated k times is a substring of sequence. The word's maximum k-repeating value is the highest value k where word is k-repeating in sequence. If word is not a substring of sequence, word's maximum k-repeating value is 0.

Given strings sequence and word, return the maximum k-repeating value of word in sequence.

Example 1:

Input: sequence = "ababc ", word = "ab " Output: 2 **Explanation: ** "abab " is a substring in "ababc ".

Example 2:

Input: sequence = "ababc ", word = "ba " Output: 1 **Explanation: ** "ba " is a substring in "ababc ". "baba " is not a substring in "ababc ".

Example 3:

Input: sequence = "ababc ", word = "ac " Output: 0 **Explanation: ** "ac " is not a substring in "ababc ".

Constraints:

  • 1 <= sequence.length <= 100
  • 1 <= word.length <= 100
  • sequence and word contains only lowercase English letters.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=*) :: sequence, word
    integer :: k_repeating

    ! Example 1
    sequence = 'ababc '
    word = 'ab '
    print *, max_k_repeating(sequence, word)

    ! Example 2
    sequence = 'ababc '
    word = 'ba '
    print *, max_k_repeating(sequence, word)

    ! Example 3
    sequence = 'ababc '
    word = 'ac '
    print *, max_k_repeating(sequence, word)

contains

    function max_k_repeating(sequence, word) result(k_repeating)
        implicit none
        character(len=*), intent(in) :: sequence, word
        integer :: k_repeating

        integer :: i, j, k

        k_repeating = 0
        do k = 1, len(sequence)-len(word)+1
            do i = 1, len(word)
                j = k + (i-1)*k
                if (sequence(j:j+len(word)-1) /= word) exit
            end do
            if (i == len(word)+1) then
                k_repeating = max(k_repeating, k)
            end if
        end do
    end function max_k_repeating

end program main
❌ Compiled
❌ Executed
❌ Correct 
module k_repeating_word

implicit none

contains

integer function k_repeating_word(sequence, word) result(max_k_repeating)

character(len=*), intent(in) :: sequence
character(len=*), intent(in) :: word

integer :: i, j, k
logical :: found

max_k_repeating = 0

do k = 1, len(sequence) - len(word) + 1

    found = .false.

    do i = 1, k

        do j = 1, len(word)

            if (sequence(i + j - 1:i + j - 1) /= word(j:j)) then
                exit
            end if

            if (j == len(word)) then
                found = .true.
                exit
            end if

        end do

        if (found) exit

    end do

    if (found) then
        max_k_repeating = max(max_k_repeating, k)
    end if

end do

end function k_repeating_word

end module k_repeating_word

program test

use k_repeating_word

implicit none

character(len=100) :: sequence, word
integer :: max_k_repeating

sequence = "ababc "
word = "ab "
max_k_repeating = k_repeating_word(sequence, word)
write (*,*) "Maximum k-repeating value of '", word, "' in '", sequence, "' is ", max_k_repeating

sequence = "ababc "
word = "ba "
max_k_repeating = k_repeating_word(sequence, word)
write (*,*) "Maximum k-repeating value of '", word, "' in '", sequence, "' is ", max_k_repeating

sequence = "ababc "
word = "ac "
max_k_repeating = k_repeating_word(sequence, word)
write (*,*) "Maximum k-repeating value of '", word, "' in '", sequence, "' is ", max_k_repeating

end program test
🌐 Data from online sources 
def longestAwesomeSubstring(s):
    n = len(s)
    maxLen = 0
    for i in range(n):
        for j in range(i + 1, n + 1):
            substr = s[i:j]
            if isAwesome(substr):
                maxLen = max(maxLen, j - i)
    return maxLen

def isAwesome(s):
    odd_count = 0
    freq = [0] * 26
    for c in s:
        freq[ord(c) - ord('a')] += 1
    for i in range(26):
        if freq[i] % 2 == 1:
            odd_count += 1
    return odd_count <= 1

The algorithm starts by checking all possible substrings of the given string s. For each substring, it checks whether it's an awesome substring or not by calling the isAwesome function. The isAwesome function calculates the frequency of each character in the string and counts the number of characters that have an odd frequency. If there are more than one characters with odd frequency, it returns false, otherwise, it returns true. Finally, the algorithm returns the length of the longest awesome substring found.

🌐 Data from online sources 
int longestAwesomeSubstring(std::string s) {
    int n = s.length();
    int maxLen = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            std::string substr = s.substr(i, j - i);
            if (isAwesome(substr)) {
                maxLen = std::max(maxLen, j - i);
            }
        }
    }
    return maxLen;
}

bool isAwesome(std::string s) {
    int odd_count = 0;
    int freq[26] = {0};
    for (char c : s) {
        freq[c - 'a']++;
    }
    for (int i = 0; i < 26; i++) {
        if (freq[i] % 2 == 1) {
            odd_count++;
        }
    }
    return (odd_count <= 1);
}

The algorithm starts by checking all possible substrings of the given string s. For each substring, it checks whether it's an awesome substring or not by calling the isAwesome function. The isAwesome function calculates the frequency of each character in the string and counts the number of characters that have an odd frequency. If there are more than one characters with odd frequency, it returns false, otherwise, it returns true. Finally, the algorithm returns the length of the longest awesome substring found.