From b4c9537fd8f13fcfc990f03b3731950fb6ae3759 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Wed, 18 Dec 2024 10:56:03 -0700 Subject: 1069. repetitions --- introductory_problems/readme.md | 7 +++++++ introductory_problems/repetitions.cpp | 16 ++++++++++++++++ 2 files changed, 23 insertions(+) create mode 100644 introductory_problems/repetitions.cpp diff --git a/introductory_problems/readme.md b/introductory_problems/readme.md index d276f99..78e52cb 100644 --- a/introductory_problems/readme.md +++ b/introductory_problems/readme.md @@ -13,3 +13,10 @@ You are given all numbers between `1, 2, ..., n` except one. Your task is to fin **Input**: The first input line contains an integer `n`. The second input line contains `n - 1` numbers. Each number is distinct and between 1 and `n` (inclusive). (Example: 5`\n`2 3 1 5) **Output**: Print the missing number. (Example: 4) + +### Repetitions +You are given a DNA sequence: a string consisting of A, C, G, and T. Your task is to find the longest repetition in the sequence. This is a maximum-length substring containing only one type of character. + +**Input**: The only input line contains a string of `n` characters. (Example: ATTCGGGA) + +**Output**: Print one integer: the length of the longest repetition. (Example: 3) diff --git a/introductory_problems/repetitions.cpp b/introductory_problems/repetitions.cpp new file mode 100644 index 0000000..ab90db9 --- /dev/null +++ b/introductory_problems/repetitions.cpp @@ -0,0 +1,16 @@ +// 1069. Repetitions +#include +using namespace std; + +const int max_size = 1e6 + 5; + +int main() { + char str[max_size]; + scanf(" %s", str); + int num = strlen(str), curr = 1, cnt = 1; + for (int i = 1; i < num; i++) { + curr = str[i] == str[i - 1] ? curr + 1 : 1; + cnt = max(cnt, curr); + } + printf("%d\n", cnt); +} -- cgit v1.2.3