Pangrams
All topics
String Basics
A string is traditionally a sequence of characters, either as a literal constant or as some kind of variable. The latter may allow its elements to be mutated and the length changed, or it may be fixed (after creation).
Some languages provide strings as a builtin datatype ( Like C++ , Java , C# ) whereas some implements string as an array of characters ( Like C ).
Strings are not available in C instead, we use a char array to read strings, where the end of string is marked with the special character \0
often called as null character.
When we have a char arr[] in C and want to iterate over the characters with a loop like
for (int i = 0;i < strlen(arr);i++){
printf("%c",arr[i]) ;
}
we have to be careful because by using strlen(arr), the complexity of the operation goes unknowingly up to . That is because strlen(arr) is a operation in itself, so it should not be used in the termination condition.
int len = strlen(arr) ;
for (int i = 0;i < len;i++){
printf("%c",arr[i]) ;
}
Substring:
A substring is a part of string such that . It is a contiguous slice of the original string.
For example : List of substrings of string S = "abc" contains following strings.
- a
- b
- c
- ab
- bc
- abc
Therefore, a string of length contains substrings.
Subsequence:
A subsequence is a sequence that can be derived from another sequence by deleting some elements ( possibly zero but not all ) without changing the order of the remaining elements.
For example : List of subsequences of string S = "abc" contains following sequences.
- a
- b
- c
- ab
- bc
- ac
- abc
Therefore, a sequence of size contains subsequences.
Subset:
Subset is any unordered set of elements from the original list.
For example : List of subsets of string S = "abc" contains following sets.
- {}
- {a}
- {b}
- {c}
- {c,b}
- {a,b}
- {a,c}
- {a,b,c}
Therefore, a set of size contains subsets.
NOTE :
- {b,a,c} is a subset of string "abc" but not a subsequence.
- Each subsequence of a collection of elements is its subset also, but reverse does not hold.
Sublist:
Sublist is any unordered list derived from the original list. Here elements need not be unique, but should exist on separate indices in the original list.
Alphabets
The English alphabet contains characters with ascii values 65 to 90 for A to Z, and 97 to 122 for a to z.
48 - 57 is for numbers (0 to 9).
Ascii set is important in many string problems where we either store characters as integers in a hash array.
Many times, when the string is of large length and we need to perform operations such as operating on a character basis and order is not important, we can store the whole string in an array of 26 elements where the value of each cell is the count of the corresponding character in the string.
Set
Set is an abstract data type that only stores unique elements. In C++ sets are implemented as a binary search tree and the elements can be accessed in a sorted order.
In Python sets are unordered.
In general, operation complexity in a set is as follows:
insert : O(logn)
delete : O(logn)
lookup : O(logn)
In Python sets are mathematical sets which also support set difference and set intersection.
Sets have a varient Multiset that also stores multiple values.
Set ADT can be used in computations where you are dealing with unique elements.