String basic formulas

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.

1. a
2. b
3. c
4. ab
5. bc
6. 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.

1. a
2. b
3. c
4. ab
5. bc
6. ac
7. 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.

1. {}
2. {a}
3. {b}
4. {c}
5. {c,b}
6. {a,b}
7. {a,c}
8. {a,b,c}

Therefore, a set of size  contains  subsets.

NOTE :

1. {b,a,c} is a subset of string "abc" but not a subsequence.
2. 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.

Source : Hackerrank.com