What's up everyone. Sam here from Byte-by-Byte.com and today I want to tell you about the five string patterns that you
absolutely have to know to master string interview questions. Plus if you stick
around to the end I'm gonna share with you the one mistake that I see people
making time and time again when they are doing string interview questions. Alright let's get into the meat of
this. But before we actually get into what the five patterns are, I want to
tell you something that's really important. And that is that there's a
reason why I'm teaching you these five patterns and I'm not focusing on telling
everything there is to possibly know about strings. And that reason is simply
that for most topics you don't need to know everything about the topic. It's
much more important that you understand the fundamentals and the core patterns,
then understand everything. So if you understand what we talk about in this
video, that's going to get you about 80% of the way there. And then you can
supplement with additional information as needed. But this is going to give you
a really good starting point. And if you enjoy what you're seeing in this video
we also have a blog post that covers this and a lot more in a lot more detail
so you can click that in the description below, or go to byte-by-byte.com/strings. And you will find that. So let's get into the five patterns the very
first pattern that you want to use a lot when you're interviewing and doing
string problems is using a length 256 integer array to represent character
counts. Or to use to basically track characters in a string. And so if you
think about it, a simple example of this would be if we wanted to find all the
anagrams. Or if we wanted to find if two strings were anagrams. An anagram is
basically two strings they have the same characters but they're in a different
order. And so one way that we can do that would be to count all the characters. And
the obvious way to do that might be do to use a hash table. Right we could
create a hash table and we would basically just map character to count of
the number of occurrences of that character. And then we could compare both
strings. And so that would work. But another way that we can do this and we
can do this because we have a fixed number of characters. Whether it's 256 in
the case of ASCII or if we were using Unicode we would have some larger set.
But we have a fixed sized number of characters that we could use. And we can
create an integer array and basically use the character as the index and the
counts as the value in that array. And so what we would do is we would create
that array and then we would look up. You know for if letter is like the integer
value 53 or something. We would look that up as the index of our array, and then we
would look up the character count. And so this is a really good strategy that we
can use in a lot of cases. Because using an array has way less overhead than
using a hash table. And especially if we have a lot of characters, it's going to
just make our lives a lot easier to work with that. The second pattern that you
should absolutely be aware of is using two pointers in a string. And this is
something that you may have come across if you've been doing any linked list
problems. But it's very similar in a string where we might use two different
pointers, to accomplish something in our string. The perfect example of this is if
we wanted to reverse a string. Now imagine that we or if we wanted to maybe
a better example would be if we wanted to reverse like in an array. What we can do
is we can have pointers at either end, and we can walk those pointers towards
each other. And basically just swap the values at those pointers. And by doing
that by using those two pointers we can accomplish the exact same thing that we
would accomplish otherwise. But it's going to be a lot easier for us. And
there are a lot of different examples of how you might use multiple pointers. So
like if you wanted to find all the duplicates in a string without using any
extra space, that's an easy way to do it. And a lot of other things that I talked
about in the blog post. The next pattern that you should be aware of is just
generally how to do string math and how to use, how to convert between like
characters and integers and all this sort of fun stuff. It's something that
ends up being kind of a pain in a lot of languages because it's just there's
there can be a lot of complexity or a lot of confusion over when a character's
handled as a character versus an integer versus a byte versus any of these
different type data types. And so the key thing here is just to understand how
your language how your chosen programming language is going to treat that. And so
like as we were talking about using a length 256 array you need to actually be
able to take that character and convert it into its ASCII value.
Right so that's something that we're going to need to be able to do easily.
And one potential way that we can do that in a lot of languages is you could
just subtract characters. So for example if you wanted to figure out what was the
like the index of a character in the alphabet you could take that character
and you could subtract capital A from that character and it would give you the
index. So understanding these sorts of little tricks is really valuable and
also being able to do things like convert a digit character into the
actual digit. So like if we wanted to convert between a string number and the
actual integer value, we would need to be able to get the values of those digits.
And so understanding this sort of thing in your strings is really valuable. The
next thing, the fourth pattern that we want to understand is generally doing
string comparison and alignment and matching. And this is something that
comes up a lot and this is going to be similar to our two pointers, except that
now we actually have two different strings. And so in most of these cases
we're gonna have a pointer into each string, and we're gonna use those to sort
of line up the strings and compare them. And so some examples of problems that
might involve this pattern are gonna be the longest common substring problem, the
edit distance problem, anything where we're comparing two strings and trying
to find what are the similarities between them.
You're also when you get to this point you're going to be drawing a lot of
recursion stuff as well, which tends to make it a lot more difficult. And so
you're definitely going to want to check out the post that we wrote and I'll put
a description in the description as well. This post that we recently published on
recursion. Which you can get to a byte-by-byte.com/recursion. It's going to
give you a lot more in-depth look at how you can use recursion with these string
problems and also a lot of other things. Finally the last pattern that I want to
talk about and I want to make sure that we're all on the same page with this. Is
just string algorithms in general. So there are algorithms that you've
probably heard of like knuth-morris-pratt, there's boyer moore, there's rabin karp. And there are a bunch of other
algorithms that maybe it would be good to know.
Right? And the key thing here is that whenever you are studying like these
named algorithms, you really want to focus more on what is the underlying
strategy here? What are the underlying techniques that I can learn from? Rather
than trying to actually memorize the entire algorithm. And that's just because
it's very unlikely that you would actually be asked to like implement boyer
or moore for example in your interview. However by studying these algorithms you
can learn what were the strategies that these people use in these algorithms. And
what are their additional patterns or are there little things that I can learn
from them that I could apply to other sorts of problems. So when you're
thinking about these string algorithms, don't worry so much about do I remember
the exact algorithm? Do I remember the name of the algorithm, but focus much
more on do I understand the concepts and can I apply those concepts? So those are
the five patterns that you need to know using a length 256 array, using two
pointers, doing string math, string comparison, and string algorithms. And now
I promised you that I would tell you the biggest mistake that I see people making
with strings and the number one mistake that you need to be really careful about
is time complexity. And the reason for this is that strings are different than
most of the other data types that we work with. Or most of the other simple
data types we work with. Like we're used to working with integers and long's and
characters and floats and all these things. And those are all fixed size data
types. Right like obviously there may be
different implementations that are a different size, but for the most part we
know what size they are. But with strings a string can be any
number of characters. A string is functionally much more like an array
than it is like a primitive data type. And therefore we need to be really
careful about how that affects our time complexity. Because things that might
seem simple or that are normally going to take constant time, can actually take
longer. So let's think about an example of this. Like a very simple example of
this would be just comparing two strings together. Now we're used to
with integers or with floats, that taking constant time right. Comparing two values
it just takes constant time. But with a string we actually have to go through
and compare all the characters. Which is going to mean that all of the sudden are
very simple operation is taking linear time and not constant time. And we may
not notice that or that may not be obvious because we're just using this
simple function that we're used to treating as being a constant time
function. Another perfect example of that is using strings as keys in a hash table.
And if you think about it when we are putting something into a hash table we
have to take the value and we have to hash it. And how long does it take to
have a string? Well again we're used to treating hash tables as this oh of one time
lookup. But in most cases if we want to come up with a good hashing algorithm,
we're actually going to have to go through the full length of the string.
And so this is another example where we think logically based on our past
experience that it's going to take constant time, but it actually takes
linear time. And so the key thing when you're doing string problems is to be
super, super careful that you are actually making sure that you are
accounting for any extra time complexity that you're using. So that's all I got
for you today. I hope you enjoyed this video. If you did please give us a
subscribe down below. And I also would love for you to check out our free guide
on 51 questions that you can that you are most likely to get asked in your
interview. So if you go over you can download that now and get those
questions. There are video responses to each one of them. I know you're going to
enjoy that, and I appreciate you joining me today. I look forward to talking to
you again soon. you
