{"problem":{"name":"DNA Sequence","description":{"content":"We have a string $S$ of length $N$ consisting of `A`, `T`, `C`, and `G`. Strings $T_1$ and $T_2$ of the same length are said to be complementary when, for every $i$ ($1 \\leq i \\leq l$), the $i$\\-th ch","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc104_b"},"statements":[{"statement_type":"Markdown","content":"We have a string $S$ of length $N$ consisting of `A`, `T`, `C`, and `G`.\nStrings $T_1$ and $T_2$ of the same length are said to be complementary when, for every $i$ ($1 \\leq i \\leq l$), the $i$\\-th character of $T_1$ and the $i$\\-th character of $T_2$ are complementary. Here, `A` and `T` are complementary to each other, and so are `C` and `G`.\nFind the number of non-empty contiguous substrings $T$ of $S$ that satisfies the following condition:\n\n*   There exists a string that is a permutation of $T$ and is complementary to $T$.\n\nHere, we distinguish strings that originate from different positions in $S$, even if the contents are the same.\n\n## Constraints\n\n*   $1 \\leq N \\leq 5000$\n*   $S$ consists of `A`, `T`, `C`, and `G`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc104_b","tags":[],"sample_group":[["4 AGCT","2\n\nThe following two substrings satisfy the condition:\n\n*   `GC` (the $2$\\-nd through $3$\\-rd characters) is complementary to `CG`, which is a permutation of `GC`.\n*   `AGCT` (the $1$\\-st through $4$\\-th characters) is complementary to `TCGA`, which is a permutation of `AGCT`."],["4 ATAT","4\n\nThe following four substrings satisfy the condition:\n\n*   `AT` (the $1$\\-st through $2$\\-nd characters) is complementary to `TA`, which is a permutation of `AT`.\n*   `TA` (the $2$\\-st through $3$\\-rd characters) is complementary to `AT`, which is a permutation of `TA`.\n*   `AT` (the $3$\\-rd through $4$\\-th characters) is complementary to `TA`, which is a permutation of `AT`.\n*   `ATAT` (the $1$\\-st through $4$\\-th characters) is complementary to `TATA`, which is a permutation of `ATAT`."],["10 AAATACCGCG","6"]],"created_at":"2026-03-03 11:01:14"}}