README_EN.md

1668. Maximum Repeating Substring

中文文档

Description

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.

Solutions

Python3

Java

C++

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int n = nums.size();
        int sum = 0;
        for (int num: nums) {
            sum += num;
        }

        int target = sum - x;
        int res = -1;
        int l = 0;
        int r = 0;
        sum = 0;
        while (r < n) {
            sum += nums[r++];
            while (sum > target && l < n) {
                sum -= nums[l++];
            }
            if (sum == target) {
                res = max(res, r - l);
            }
        }

        if (res == -1) {
            return res;
        }
        return n - res;
    }
};

TypeScript

function minOperations(nums: number[], x: number): number {
    const n = nums.length;
    const target = nums.reduce((r, v) => r + v) - x;

    let l = 0;
    let r = 0;
    let sum = 0;
    let max = -1;
    while (r < n) {
        sum += nums[r++];
        while (sum > target && l < r) {
            sum -= nums[l++];
        }

        if (sum === target) {
            max = Math.max(max, r - l);
        }
    }

    if (max === -1) {
        return max;
    }
    return n - max;
}

Rust

impl Solution {
    pub fn min_operations(nums: Vec<i32>, x: i32) -> i32 {
        let n = nums.len();
        let target = nums.iter().sum::<i32>() - x;

        let (mut l, mut r) = (0, 0);
        let (mut sum, mut max) = (0, -1);
        while r < n {
            sum += nums[r];
            r += 1;
            while sum > target && l < r {
                sum -= nums[l];
                l += 1;
            }

            if sum == target {
                max = max.max((r - l) as i32);
            }
        }

        if max == -1 {
            return max;
        }
        return n as i32 - max;
    }
}

...