Advanced Algorithms (Winter 2026-27) - 04-07 Depth-Bounded Search for Closest String
Watch on YouTube →
Overview
Closest String asks whether there is a length-L string within Hamming distance K of each of M input strings. A depth-bounded search starts from the first input string, uses dirty-column and triangle-inequality checks to prune impossible instances, and branches on K+1 mismatch positions; its search tree has size O(K^K), with distances maintainable incrementally.
Key takeaways
- In Closest String, every dirty column forces at least one mismatch among the M rows, so more than M·K dirty columns proves that no consensus can be within distance K of every row.
- A candidate with D edits remaining can be rejected when an input is more than K+D away, because even spending every remaining edit cannot reduce its distance to K.
- If an input differs from the current candidate in K+1 selected positions, any valid consensus must correct at least one selected position, making those positions a complete branching set.
- The branching factor K+1 and maximum depth K yield O((K+1)^K), equivalently O(K^K), search-tree size.
- Hamming distance is a metric: any pair of inputs farther than 2K apart cannot both be within K of a shared consensus.
- Updating the candidate at only one character position allows its distances to all M input strings to be maintained incrementally rather than recomputed from scratch.
Chapters
- The input is M strings of equal length L; the goal is a consensus string whose Hamming distance from every input is at most K.
- Arrange the strings as rows of a matrix and call a column dirty when its rows contain at least two different characters.
- If there are more than M·K dirty columns, no solution exists: every dirty column forces at least one mismatch across the M strings, exceeding the total M·K mismatch budget.
- Start with the first input string as the candidate S and a remaining change budget D initialized to K.
- Reject a branch if D is negative or some input string is more than K+D away from S; at most D further edits cannot bring it within distance K.
- Hamming distance satisfies the triangle inequality, so any two input strings more than 2K apart rule out a common string within distance K of both.
- If S is already within distance K of every input, return it as a valid consensus.
- When an input string differs from S in more than K positions, select K+1 of those mismatch positions; any feasible solution must change at least one of them.
- Create K+1 recursive branches, each changing one selected position to the character in the mismatching input, and reduce D by one.
- The depth is at most K, giving a search tree of size O((K+1)^K), which is O(K^K) asymptotically.
- Maintain each candidate's Hamming distance to all M inputs in an array; changing one character lets the algorithm update those distances by inspecting that position.
Transcript excerpt
0:00 In the next section we look at yet another little problem that we can give a depth bounded search tree for. Uh in this case we'll end up with an even worse running time. So so far we've seen relatively small kernels and essentially singly exponential size search trees. And so maybe you get the feeling that that's all there is and so here's a little example where it's it's worse. It's a rather hard problem. Um the problem is called closest string. Um Was it in the list of NP-hard problems as well? Uh I think it was one one variant of this at least if it's not precisely the one. So what's the input? We're given strings all of the same length L.
0:51 And M of them. And the question is is there a way to find uh some other string little S that is rather close to all of them simultaneously. And close here means I want a sort of consensus string S that has Hamming distance at most K at most K uh positions differ. Hamming distance between this say if this is S then uh for every string it has to be mostly With maybe here a mismatch if there's two different characters A and B. And so on.
1:45 Uh then the Hamming distance is just the number of positions where there's a mismatch. Because the strings are all the same length the columns are perfectly aligned. So it seems a rather innocent problem if you think about it from from that perspective um why should it be so hard? But it turns out it's it's uh it's trickier than it looks. Um some easy observations to get started. Um if we look at our M strings, it's convenient to put them in one one little
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Sebastian Wild (Lectures).