README.md

1668. 最大重复子字符串

English Version

题目描述

给你一个字符串 sequence ，如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串，那么单词 word 的 重复值为 k 。单词 word 的 最大重复值 是单词 word 在 sequence 中最大的重复值。如果 word 不是 sequence 的子串，那么重复值 k 为 0 。

给你一个字符串 sequence 和 word ，请你返回 最大重复值 k 。

 

示例 1：

输入：sequence = "ababc", word = "ab"
输出：2
解释："abab" 是 "ababc" 的子字符串。

示例 2：

输入：sequence = "ababc", word = "ba"
输出：1
解释："ba" 是 "ababc" 的子字符串，但 "baba" 不是 "ababc" 的子字符串。

示例 3：

输入：sequence = "ababc", word = "ac"
输出：0
解释："ac" 不是 "ababc" 的子字符串。

 

提示：

• 1 <= sequence.length <= 100
• 1 <= word.length <= 100
• sequence 和 word 都只包含小写英文字母。

解法

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;
    }
}

...