PCAP Strings Practice Question
A data scientist needs to count the occurrences of a substring in a long DNA sequence (e.g., 1 million bases). However, the count must include overlapping occurrences. For example, in 'AAAA', the substring 'AA' appears three times overlapping. The built-in count() method does not count overlapping matches. The scientist needs a function to count overlapping substrings efficiently without using third-party libraries. Which of the following approaches is the most efficient for this task?
⚠ Common exam trap
Python Institute often tests the distinction between overlapping and non-overlapping matches, and the trap here is that candidates assume `str.count()` or simple loops are sufficient, not realizing that overlapping matches require a zero-width assertion like lookahead in regex.
Answer choices
Why each option matters
Answer the question above first, then reveal the full breakdown to understand why each option is right or wrong.
Correct answer & explanation
✓
Use re.findall with a positive lookahead: len(re.findall(r'(?=AA)', sequence))
`re.findall` with a positive lookahead `(?=AA)` matches overlapping occurrences without consuming characters. The lookahead assertion checks for the substring at each position without advancing the match position, so every overlapping occurrence is found. This is more efficient than manual loops because the underlying regex engine is implemented in C and optimized for pattern matching.
Answer analysis
Option-by-option breakdown
For each option: why learners choose it and why it is or isn't the right answer here.
- ✗
Use a for loop with slicing and compare: sum(1 for i in range(len(s)-len(sub)+1) if s[i:i+len(sub)] == sub)
Why it's wrong here
This approach is functionally valid for counting overlapping occurrences, because the index advances by one, but it is inefficient: each iteration constructs a new substring via slicing, which requires copying up to m characters. The overall time complexity is O(n*m), and for large strings the allocation overhead and copying can become a significant performance bottleneck. Python's slicing creates a new string object each time, adding memory churn that a regex or optimized algorithm avoids.
- ✗
Use two nested loops to check all possible positions
Why it's wrong here
Using two nested loops to manually compare character-by-character at every position is the most primitive approach and suffers from poor performance. Without optimization, the worst-case time complexity is O(n*m), and if the inner loop scans the entire remaining string for every starting position, it can degrade to O(n^2). Moreover, this approach is error-prone because it requires careful index management and boundary checks, especially when dealing with overlapping matches. It offers no advantage over simpler, more efficient alternatives.
- ✓
Use re.findall with a positive lookahead: len(re.findall(r'(?=AA)', sequence))
Why this is correct
The positive lookahead (?=AA) matches the zero-width position where the substring 'AA' begins, without consuming any characters, so the regex engine can find overlapping occurrences at every starting index. re.findall returns one empty-string match for each such position, so len() gives the exact count of overlapping occurrences. This is efficient because the regex engine scans the string once in O(n) time for a literal pattern, with no substring copying or manual index stepping. It is the cleanest solution when overlapping matches must be counted.
- ✗
Use a while loop with str.find() and increment the start index by 1
Why it's wrong here
Using str.find() in a loop is a common pattern, but it has a serious performance flaw: each call to find() internally performs a substring search that can take O(n*m) time in the worst case, and repeated calls can compound that cost. If the pattern is pathological (e.g., a long prefix that matches many positions), the total runtime can approach O(n^2) or worse. Additionally, the code must be careful to increment the start index by 1 to catch overlapping matches, and any mistake can lead to missed matches or an infinite loop. While it works correctly when implemented properly, it is not the best choice for large sequences.
Go deeper
Related to this question
About these practice questions
This PCAP question is part of Courseiva's 421-question bank — original exam-style content with full explanations and wrong-answer analysis, never real exam questions or exam dumps. Learn why practice questions differ from exam dumps →
JA
Written by Johnson Ajibi, MSc IT Security
Senior Network & Security Engineer · founder of Courseiva
This PCAP practice question is part of Courseiva's free Python Institute certification practice question bank. Courseiva provides original exam-style practice questions with explanations, topic-based practice, mock exams, readiness tracking, and study analytics to help learners prepare for the PCAP exam.