[LeetCode] Maximum Repeating Substring

아르당·2026년 6월 11일

LeetCode

목록 보기
353/602
post-thumbnail

문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

문자열 sequence에서, word가 k번 반복하는 것는 word가 suquence의 부분 문자열이라는 것을 의미한다. word가 최대 k번 반복하는 값은 suquence에서 가장 많이 반복되는 횟수이다. 만약 word가 sequence의 부분 문자열이 아니라면 반복 횟수는 0이다.

문자열 sequence와 word가 주어졌을 때, sequence에서 word의 최대 반복 횟수 k를 반환해라.

Example

#1
Input: sequence = "ababc", word = "ab"
Output: 2
Explanation: "abab"는 "ababc"에서 부분 문자열이다.

#2
Input: sequence = "ababc", word = "ba"
Output: 1
Explanaiton: "ba"는 "ababc"에서 부분 문자열이다. "baba"는 "ababc"에서 부분 문자열이 아니다.

#3
Input: sequence = "ababc", word = "ac"
Output: 0
Explanation: "ac"는 "ababc"에서 부분 문자열이 아니다.

Constraints

  • 1 <= sequence.length <= 100
  • 1 <= word.length <= 100
  • sequence와 word는 오직 영어 소문자로 구성된다.

Solved

class Solution {
    public int maxRepeating(String sequence, String word) {
        int n = sequence.length();
        int m = word.length();
        int[] dp = new int[n + 1];
        int max = 0;

        for(int i = m; i <= n; i++){
            if(sequence.substring(i - m, i).equals(word)){
                dp[i] = dp[i - m] + 1;
                max = Math.max(max, dp[i]);
            }
        }

        return max;
    }
}
profile
내 마음대로 코드 작성하는 세상

0개의 댓글