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.

 
Related challenge for String Basics
Go to Top

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.

 
Related challenge for Alphabets
Go to Top

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.

 
Related challenge for Set
Go to Top
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score