Analyzing Genome Sequences — Problem Statement & Solution Guide
Problem Description
Given a string S composed exclusively of the characters 'A','C','G','T', determine the total number of contiguous substrings in which no two adjacent characters are identical. Each substring is defined by a pair of indices (l,r) with 1≤l≤r≤|S|. Return the count as a 64‑bit integer.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Analyzing Genome Sequences"
WHY DOES IT MATTER?
The pattern of counting sub‑arrays/sub‑strings with a local constraint appears in many string‑processing and array‑analysis problems; mastering it gives you a toolbox for turning quadratic combinatorial counts into linear scans.
OPTIMIZATION CHALLENGE
Recognizing that the validity of a substring depends solely on adjacent pairs lets you collapse the problem to run‑length counting, eliminating the need for nested loops and reducing time from O(n^2) to O(n).
REAL-WORLD CONNECTION
Think of a DNA sequencing pipeline where you need to detect error‑free stretches: each stretch without repeated nucleotides can be processed independently, just like a streaming service that buffers only the current uninterrupted segment to compute metrics on the fly.
During the interview, keep a running length variable, add its value to the answer after each character, and reset it when you see a repeat – this one‑liner inside the loop is both simple and hard to mess up.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem asks for the count of substrings where no two consecutive characters are the same. A naive solution would enumerate every (l,r) pair, extract the substring and scan it for adjacent equal characters, leading to O(n^2) substrings and O(n) work per substring – O(n^3) overall, which is impossible for |S| up to 10^5 or more. The key observation is that the property of “no equal neighbours” is local: a substring is valid if and only if every adjacent pair inside it differs. This allows us to treat the string as a sequence of maximal blocks where characters alternate. Within a block of length k where every adjacent pair is different, any sub‑substring is automatically valid, contributing k·(k+1)/2 substrings. When a repeat occurs (e.g., "AA"), it breaks the block, and we start a new count. By scanning the string once and maintaining the length of the current alternating segment, we can accumulate the answer in linear time. This sliding‑window / run‑length technique is a classic linear‑time pattern for counting sub‑structures defined by a local constraint.
Interview Questions on This Problem
Q1How would you modify the solution if the constraint changed to “no three consecutive characters are identical” instead of two?
Maintain a counter of consecutive identical characters; reset it to 1 when the current character differs, otherwise increment. When the counter reaches 3, the current position cannot be part of a valid substring, so you start a new segment. The contribution of each segment is still length·(length+1)/2, giving an O(n) solution.
Q2Why does a two‑pointer (sliding window) approach work for this problem, and can it be used to output the longest valid substring as well?
The window expands while the adjacency condition holds; when a violation appears, the left pointer jumps to the position after the previous character, effectively discarding the invalid prefix. Because the condition depends only on the last two characters, the window adjustments are O(1). The same window can track the maximum window size to return the longest valid substring in addition to the count.
Q3In a distributed system processing a massive genome stream, how would you compute the answer without storing the entire string?
Each node can process its chunk locally, counting alternating runs and the length of the prefix/suffix run that may extend across chunk boundaries. After processing, nodes exchange the boundary run lengths to adjust counts for substrings that span two chunks, achieving a linear‑time, O(1)‑per‑node memory solution.
Examples
Input
ACGT
Output
10
Explanation: The whole string contains no equal neighbours, therefore every possible substring (|S|·(|S|+1)/2 = 4·5/2 = 10) satisfies the condition.
Input
AAG
Output
4
Explanation: All substrings are: A, A, G, AA, AG, AAG. The ones without equal adjacent characters are the three single‑letter substrings and "AG", giving a total of 4.
Input
TTATA
Output
11
Explanation: Valid substrings are: T (pos1), T (pos2), TA, TAT, TATA, A (pos3), AT, ATA, T (pos4), TA (pos4‑5), A (pos5). Counting them yields 11.
Constraints
- 1 <= |S| <= 200000
- S consists only of the characters 'A','C','G','T'
- Result fits in a signed 64‑bit integer
Optimal Approach & Strategy
Maintain the length of the current alternating segment while scanning; each new character contributes its segment length to the total, resetting on a repeat – O(n) time, O(1) space.
Brute Force Approach
Generate every possible (l,r) pair, extract the substring and check each adjacent pair for equality – O(n^3) time.
Verified Code Solutions
function countValidSubstrings(s) {
let total = 0n;
let cur = 0n;
for (let i = 0; i < s.length; ++i) {
if (i === 0 || s[i] !== s[i-1]) {
cur = cur + 1n;
} else {
cur = 1n;
}
total += cur;
}
return total.toString();
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim();
if (input.length===0) {
console.log(0);
} else {
console.log(countValidSubstrings(input));
}#include <bits/stdc++.h>
using namespace std;
long long countValidSubstrings(const string& s) {
long long total = 0, cur = 0;
for (size_t i = 0; i < s.size(); ++i) {
if (i == 0 || s[i] != s[i-1]) cur += 1; else cur = 1;
total += cur;
}
return total;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
if(!(cin>>s)) return 0;
cout << countValidSubstrings(s) << "\n";
return 0;
}import java.io.*;
public class Main {
static long countValidSubstrings(String s) {
long total = 0;
long cur = 0;
for (int i = 0; i < s.length(); i++) {
if (i == 0 || s.charAt(i) != s.charAt(i-1)) {
cur += 1;
} else {
cur = 1;
}
total += cur;
}
return total;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
if (s == null) s = "";
System.out.println(countValidSubstrings(s.trim()));
}
}def count_valid_substrings(s: str) -> int:
total = 0
cur = 0
for i, ch in enumerate(s):
if i == 0 or ch != s[i-1]:
cur += 1
else:
cur = 1
total += cur
return total
def main():
import sys
data = sys.stdin.read().strip()
if not data:
print(0)
return
print(count_valid_substrings(data))
if __name__ == "__main__":
main()function countValidSubstrings(s) {
let total = 0n;
let cur = 0n;
for (let i = 0; i < s.length; ++i) {
if (i === 0 || s[i] !== s[i-1]) {
cur = cur + 1n;
} else {
cur = 1n;
}
total += cur;
}
return total.toString();
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim();
if (input.length===0) {
console.log(0);
} else {
console.log(countValidSubstrings(input));
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.