Hi everyone.
Welcome to this Data Structures Crash Course video where we are discussing strings.
Now typically you may think of strings as a data type like boolean or number etc. then strings are similar
to data structures in that we can manipulate them just like we can manipulate an array.
Now how do we store strings?
Strings actually are stored as an array of integers, and for getting these integers, each character
in the string is converted into an integer using a mapping.
Now let's take a look at the Big-O analysis of common operations on strings.
Now, when it comes to reading the character at a given index, it's a constant time and space operation.
Because a string is stored as an array of integers in memory.
All right.
And to get again these integers, every character in the string is converted into an integer.
So it's just stored as an array.
Therefore, if we know the index we can access the character at that particular index in constant time
and constant space.
Again, it's constant space because we are not using any auxiliary space.
Now, accessing an element at a particular index is constant time in the case of an array.
All right.
Now let's proceed.
If you want to traverse a string again because it's stored as an array, this is going to be an O of
n time complexity operation.
And the space complexity is O of one because we are not using any auxiliary space.
Now, if you want to copy a string and create a new string again, it's going to be an O of n time complexity
operation because we have to traverse the string.
And then it's going to take O of N space as well because we have to make a copy.
Now these are the two interesting operations over here appending and concatenating.
Now if you want to do this, the interesting thing to notice over here is depending on the programming
language which you are using, strings are going to be either mutable or immutable.
Now let's say the language is something like C plus plus.
In that case, strings are mutable, but in JavaScript or Python or Java etc., strings are immutable.
Now, when we say that a string is immutable, what we mean is that after we create a string, we cannot
modify it.
Now therefore, if in any of these languages we are trying to modify a string after we create it, what's
actually happening is we are creating a new string with the required property.
All right.
So let's take an example to understand this.
Now let's say we say that we have a string newest okay new string.
So I'm just abbreviating it to newest.
Now let's say it's j o h.
And then we are appending n to it.
All right.
We are adding n to j or h to get John.
Now this over here is not a constant time operation, even though we are adding or appending at the
end.
That's because in languages such as JavaScript, strings are immutable.
So what's happening over here is an O of n time operation, which is appending at the end of the string.
So again what happens when we do this.
Actually this string over here is copied and a new string is created along with n which is this n over
here.
So that is what happens when we try to append.
So this is an O of n time operation.
And similarly when we try to concatenate two strings again the time complexity is going to be o of n
plus m, where n and m are the respective lengths of the two strings.
Again, why is that so?
Because we cannot modify the strings.
We have to create a new string of length n plus m.
That's why we have space complexity of O of n plus m, because again we are trying to concatenate and
the time complexity is also O of n plus m, because we have to traverse both these strings separately
and then make a copy and create the new string.
All right.
Now with respect to this, if you have an question, if you're dealing with an algorithm question,
and if you want to do many modifications to a string with respect to time complexity, because what
we have seen in the case of appending and concatenating, it's better to convert the string to an array.
And then you can do the modifications.
And after you are done, you can join it together and make a string.
Now we will see this in one of the practice questions in this section.