4.3.2. Case When Characters Do Not Match

So, we can now look at a slightly more general problem than longest common subword in one which is more interesting computationally. So, what if we do not look for an exact match, but we allow a self should drop some letters. So, we have a subsequence not a sub word, it is allows us to drop some letters and now, if you want to know, after dropping some letters, what is the longest match we can find.

In this chunk, we are exploring a variation of the longest common subsequence problem. Unlike in previous approaches where we look for exact matches between characters, we now allow for some flexibility: we can drop letters. This means that instead of finding consecutive characters that match exactly, we are interested in finding the longest sequence of characters that can match even if some characters are left out in between. The question we now ask is: after dropping some letters, what is the longest sequence we can still match?

Imagine you and a friend are trying to find a common interest but in the middle of your conversation, you might forget to mention a few hobbies you had. However, if you focus on the interests you remember, you might discover that you both enjoy painting, even if the full list of hobbies doesn't match perfectly.

So, now, our earlier example, some of them are the same, like in this case without dropping any letter I can could get 6, I cannot improve it, same we will bisect, I cannot improve it. But, now if I look at bisect and secret, earlier we only had a length 3 match sec, sec, but now I can extend match the length 4, because here if we add it t, here I can drop two letters and get it t.

This chunk discusses an illustrative example where, by allowing some letters to be dropped (i.e., not requiring an exact match), we can potentially find longer matching subsequences. For instance, in comparing the words 'bisect' and 'secret', we find that they initially share a matching subsequence of length 3 ('sec'). However, by dropping certain letters, we can extend this match to include an additional character, resulting in a subsequence of length 4. This showcases how dropping letters can lead to discovering longer matches between two sequences.

Think of it like two people telling a story. One person might forget certain details while narrating, but they both may remember key events. By focusing on the main events and ignoring the minor details that were left out, they can still construct a coherent narrative together, revealing more connections than if they strictly adhered to a perfect retelling.

So, before we proceed it useful to look at why the longest common subsequence problem is interesting. So, one of the area is bio informatics. So, biologist are interested in identifying, how close two species are each other in the genetic sense.

This chunk highlights the practical significance of the longest common subsequence (LCS) problem. One critical application is in bioinformatics, where scientists compare DNA sequences to determine how closely related different species are. DNA consists of sequences of nucleotides represented by the letters A, T, G, and C. By identifying the longest common subsequence between two DNA strands, researchers can infer genetic relationships and evolution.

Analogous to searching for common language traits in two dialects, biologists study genetic sequences to trace common ancestry – like piecing together a family tree. Just as one might look for similarities in dialects to understand cultural connections, scientists look for similarities in DNA to understand biological connections.

So, the first thing to note is that if I am looking for this longest common subword between these two, supposing I find that a 0, in fact equal to b 0. Now, I claim that, I should combine them in the solution, and then look for a solution in the rest.

This chunk introduces a methodical approach to tackling the LCS problem using an inductive structure. The rationale is simple: if the first characters of both sequences match (let's say a[0] and b[0]), it indicates that these characters can be part of the longest common subsequence. After including these characters in the solution, we then look at the remaining characters from both sequences to find additional matches. This builds towards a complete solution by constructing subproblems that reflect the overall goal.

Consider building a puzzle. If you correctly place the first piece because it fits, you not only celebrate that success but also choose to work on the remaining pieces to complete the picture. Each correct placement creates an opportunity to find more matching pieces, just like finding successive matches in the LCS problem.

Now, if it is not equal, then one is not sure what you do, it is not sound idea to drop both. So, for instant supposing I have something like straw and astray, then just because the S does not match the a, does not mean that I should in both of them, I should keep that S alive to match with next S.

This chunk tackles the scenario where the first characters of the sequences do not match. In this case, rather than dropping both characters which might cause a loss of potentially important matches, we need to keep one character and explore further possibilities. For example, if we compare 'straw' with 'astray', the characters 'S' and 'a' do not match, but keeping 'S' might allow us to find matches later on. Therefore, we create two new subproblems: one excluding the first character of the first sequence and another excluding the first character of the second sequence.

Think of this as a game of finding commonalities in two different playlists of songs. Just because the first song on one playlist isn't on the other doesn’t mean it doesn’t have value. Instead of removing it, you search for connections in other songs that might reveal a similar taste in music, enriching your understanding of both playlists.

--