1
00:00:00,790 --> 00:00:01,750
Hi everyone.

2
00:00:01,750 --> 00:00:06,940
Welcome to this Data Structures Crash Course video where we are discussing strings.

3
00:00:06,970 --> 00:00:14,260
Now typically you may think of strings as a data type like boolean or number etc. then strings are similar

4
00:00:14,260 --> 00:00:20,080
to data structures in that we can manipulate them just like we can manipulate an array.

5
00:00:20,110 --> 00:00:22,060
Now how do we store strings?

6
00:00:22,090 --> 00:00:28,660
Strings actually are stored as an array of integers, and for getting these integers, each character

7
00:00:28,660 --> 00:00:32,380
in the string is converted into an integer using a mapping.

8
00:00:32,380 --> 00:00:37,930
Now let's take a look at the Big-O analysis of common operations on strings.

9
00:00:37,960 --> 00:00:44,140
Now, when it comes to reading the character at a given index, it's a constant time and space operation.

10
00:00:44,140 --> 00:00:48,400
Because a string is stored as an array of integers in memory.

11
00:00:48,400 --> 00:00:48,730
All right.

12
00:00:48,730 --> 00:00:54,070
And to get again these integers, every character in the string is converted into an integer.

13
00:00:54,070 --> 00:00:56,140
So it's just stored as an array.

14
00:00:56,140 --> 00:01:02,080
Therefore, if we know the index we can access the character at that particular index in constant time

15
00:01:02,080 --> 00:01:03,190
and constant space.

16
00:01:03,190 --> 00:01:06,670
Again, it's constant space because we are not using any auxiliary space.

17
00:01:06,670 --> 00:01:12,010
Now, accessing an element at a particular index is constant time in the case of an array.

18
00:01:12,010 --> 00:01:12,520
All right.

19
00:01:12,550 --> 00:01:13,540
Now let's proceed.

20
00:01:13,540 --> 00:01:18,730
If you want to traverse a string again because it's stored as an array, this is going to be an O of

21
00:01:18,730 --> 00:01:20,710
n time complexity operation.

22
00:01:20,710 --> 00:01:25,450
And the space complexity is O of one because we are not using any auxiliary space.

23
00:01:25,450 --> 00:01:31,540
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

24
00:01:31,540 --> 00:01:33,940
operation because we have to traverse the string.

25
00:01:33,940 --> 00:01:38,320
And then it's going to take O of N space as well because we have to make a copy.

26
00:01:38,320 --> 00:01:42,580
Now these are the two interesting operations over here appending and concatenating.

27
00:01:42,580 --> 00:01:48,670
Now if you want to do this, the interesting thing to notice over here is depending on the programming

28
00:01:48,670 --> 00:01:54,430
language which you are using, strings are going to be either mutable or immutable.

29
00:01:54,430 --> 00:01:57,490
Now let's say the language is something like C plus plus.

30
00:01:57,490 --> 00:02:04,930
In that case, strings are mutable, but in JavaScript or Python or Java etc., strings are immutable.

31
00:02:04,930 --> 00:02:10,990
Now, when we say that a string is immutable, what we mean is that after we create a string, we cannot

32
00:02:10,990 --> 00:02:11,650
modify it.

33
00:02:11,680 --> 00:02:17,890
Now therefore, if in any of these languages we are trying to modify a string after we create it, what's

34
00:02:17,890 --> 00:02:22,090
actually happening is we are creating a new string with the required property.

35
00:02:22,090 --> 00:02:22,630
All right.

36
00:02:22,630 --> 00:02:25,120
So let's take an example to understand this.

37
00:02:25,120 --> 00:02:28,990
Now let's say we say that we have a string newest okay new string.

38
00:02:28,990 --> 00:02:31,060
So I'm just abbreviating it to newest.

39
00:02:31,090 --> 00:02:33,040
Now let's say it's j o h.

40
00:02:33,040 --> 00:02:34,870
And then we are appending n to it.

41
00:02:34,870 --> 00:02:35,260
All right.

42
00:02:35,260 --> 00:02:37,720
We are adding n to j or h to get John.

43
00:02:37,720 --> 00:02:43,360
Now this over here is not a constant time operation, even though we are adding or appending at the

44
00:02:43,360 --> 00:02:43,660
end.

45
00:02:43,690 --> 00:02:48,160
That's because in languages such as JavaScript, strings are immutable.

46
00:02:48,160 --> 00:02:53,950
So what's happening over here is an O of n time operation, which is appending at the end of the string.

47
00:02:53,950 --> 00:02:56,590
So again what happens when we do this.

48
00:02:56,590 --> 00:03:02,860
Actually this string over here is copied and a new string is created along with n which is this n over

49
00:03:02,860 --> 00:03:03,160
here.

50
00:03:03,160 --> 00:03:05,770
So that is what happens when we try to append.

51
00:03:05,770 --> 00:03:08,260
So this is an O of n time operation.

52
00:03:08,260 --> 00:03:14,500
And similarly when we try to concatenate two strings again the time complexity is going to be o of n

53
00:03:14,500 --> 00:03:19,120
plus m, where n and m are the respective lengths of the two strings.

54
00:03:19,120 --> 00:03:20,110
Again, why is that so?

55
00:03:20,110 --> 00:03:21,940
Because we cannot modify the strings.

56
00:03:21,940 --> 00:03:25,450
We have to create a new string of length n plus m.

57
00:03:25,840 --> 00:03:31,240
That's why we have space complexity of O of n plus m, because again we are trying to concatenate and

58
00:03:31,240 --> 00:03:36,850
the time complexity is also O of n plus m, because we have to traverse both these strings separately

59
00:03:36,850 --> 00:03:40,030
and then make a copy and create the new string.

60
00:03:40,030 --> 00:03:40,510
All right.

61
00:03:40,540 --> 00:03:46,240
Now with respect to this, if you have an question, if you're dealing with an algorithm question,

62
00:03:46,240 --> 00:03:52,390
and if you want to do many modifications to a string with respect to time complexity, because what

63
00:03:52,390 --> 00:03:58,000
we have seen in the case of appending and concatenating, it's better to convert the string to an array.

64
00:03:58,390 --> 00:04:01,060
And then you can do the modifications.

65
00:04:01,060 --> 00:04:04,660
And after you are done, you can join it together and make a string.

66
00:04:04,660 --> 00:04:08,470
Now we will see this in one of the practice questions in this section.