# Strings

## ASCII

Character sets are a set of characters that are supported by a programming language. Because computers only work with numbers, we define some sets of numbers as characters. For English, there are some standard codes which are followed by every electronic device and these codes are known as ASCII. American Standard Codes for Information Interchange is given by ANSI and ISO. ASCII for some of the alphabets and other characters are:

ASCII ranges from 0 - 127 and requires 7-bits to store in the memory. This is the reason why `char` requires 1 byte of memory space in `C/C++`.

Unicode is another character set which supports encoding for all the languages, including English, so it is a superset of ASCII. It requires 2 bytes of memory space and is represented as 4 digits of 4 bits of hexadecimal.

## Declaring and Initializing char

### i.

`char c = 'A';`

### ii.

char X[5] = {'A', 'B', 'C', 'D', 'E'};
char X[]  = {'A', 'B', 'C', 'D', 'E'};
char X[5] = {65, 66, 67, 68, 69};

All of these are valid declarations and initialization of character arrays.

### iii.

char name[10] = {'J', 'o', 'h', 'n', '\0'};

Here we have an array of size 10, but only 4 places are used, so ho we know where array ends, this is the reason we use `\0`, called `NUL` character, which indicates end of string, The main difference between `C` char array and string is the `NUL` character.

### iv.

char name[] = "John";

Here `C` compiler automatically takes care of adding `NUL` characters if the characters are in 'double quotes'.

### v.

char* name = "John";

Here the speciality is that, this string will automatically be allocated in **Heap**, even though no `malloc()` was used. It is implicitly allocated.

## Functions on String

### Length

Here we can count the numbers of characters in a string until we encounter the `\0` character.

int Length(char s[])
{
    int len = 0;
    for (int i = 0; s[i] != '\0'; i++)
    {
        len++;
    }
    return len;
}

### Changing Case

#### 1. Converting a string to Uppercase

A string with lowercase letters can be converted to uppercase letters by adding 32 to every character in the string. We add 32 because the diff b/w a(97) and A(65) is 32 and therefore it becomes capital.

void ToUpper(char s[])
{
    for (int i = 0; s[i] != '\0'; i++)
    {
        else if (s[i] >= 'a' && s[i] <= 'z')
        {
            s[i] += 32;
        }
    }
    printf("%s", s);
}

#### 2. Toggling the cases

Toggling means changing uppercase to lowercase and vice versa.
This can be done by checking if a character is uppercase and then adding 32 to it and subtracting 32 if it is lowercase.

void ToggleCase(char s[])
{
    for (int i = 0; s[i] != '\0'; i++)
    {
        if (s[i] >= 'A' && s[i] <= 'Z')
        {
            s[i] += 32;
        }
        else if (s[i] >= 'a' && s[i] <= 'z')
        {
            s[i] -= 32;
        }
    }
}

### Counting vowels & consonants

digraph D
{
    rankdir = LR
    layout = neato
    node[shape = record]

    A1 [label = "{<tag1> H|<tag2> e|<tag3> l|<tag4> l|<tag5> o|<tag6> |<tag7> W|o|r|l|d|\\0}", pos = "0,0!"]
    s[pos="-2.25,0!", color=invis]
}

int Count()
{
    int vowels = 0, count = 0;
    for(int i = 0; s[i] != '\0'; i++)
    {
        if(s[i] == 'a'
        || s[i] == 'e'
        || s[i] == 'i'
        || s[i] == 'o'
        || s[i] == 'u'
        || s[i] == 'A'
        || s[i] == 'E'
        || s[i] == 'I'
        || s[i] == 'O'
        || s[i] == 'U')
        {
            vowels++;
        }
        else if ((s[i] >= 'A' && s[i] <= 'Z')
              || (s[i] >= 'a' && s[i] <= 'z'))
        {
            count++;
        }
    }
}

### Counting Words

We can count the number of words by counting the number of spaces in the string. We check if there are two consecutive spaces and not increment words if that is true.

digraph D
{
    rankdir = LR
    layout = neato
    node[shape = record]

    A1 [label = "{<tag1> H|<tag2> e|<tag3> l|<tag4> l|<tag5> o|<tag6> ||<tag7> W|o|r|l|d|\\0}", pos = "0,0!"]
    s[pos="-2.25,0!", color=invis]
}

int WordCount()
{
    int word = 1;
    for (int i = 0; s[i] != '\0'; i++)
    {
        if (s[i] == ' ' && s[i-1 != ' '])
        {
            word++;
        }
    }
    return word;
}

### Validating a string

When creating an account on any website, we can only enter a certain type of character. To check if the user has entered a valid string, we have to _validate_ it.

digraph D
{
    rankdir = LR
    layout = neato
    node[shape = record]

    A1 [label = "{<tag1> A|<tag2> n|<tag3> i|<tag4> l|<tag5> 3|<tag6> 2|<tag7> 1| \\0}", pos = "0,0!"]
    name[pos="-1.75,0!", color=invis]
}

bool IsValid(char name[])
{
    for(int i = 0; name[i] != '\0'; i++)
    {
        if (!(name[i] >= 'A' && name[i] <= 'Z')
         && !(name[i] >= 'a' && name[i] <= 'z')
         && !(name[i] >= '0' && name[i] <= '9'))
        {
            return false;
        }
    }
    return true;
}

### Permutations of a string

digraph D
{
    rankdir=LR
    layout=neato
    node[shape=record]
    arr[label="{A|B|C|\\0}",pos="0,0!"]
    "s"[color=invis,pos="-1,0!"]

    "s" -> arr [color=invis]
}

Permutations are all the different arrangements of the given string. For the string above the different permutations will be:

1. ABC
2. ACB
3. BAC
4. BCA
5. CAB
6. CBA

The possible number of permutations for a string of any length would be $n!$ where $n$ is the number of characters and its factorial.

digraph D
{
    node[shape=ellipse,color=invis]
    edge[dir=none]

    ""[shape=circle,color=black]

    "" -> A1
    A1 -> B1
    B1 -> C1
    C1 -> "ABC"

    A1 -> C2
    C2 -> B2
    B2 -> "ACB"

    "" -> B3
    B3 -> A2
    A2 -> C3
    C3 -> "BAC"

    B3 -> C4
    C4 -> A3
    A3 -> "BCA"

    "" -> C5
    C5 -> A4
    A4 -> B4
    B4 -> "CAB"

    C5 -> B5
    B5 -> A5
    A5 -> "CBA"

    A1[label="A"]
    A2[label="A"]
    A3[label="A"]
    A4[label="A"]
    A5[label="A"]

    B1[label="B"]
    B2[label="B"]
    B3[label="B"]
    B4[label="B"]
    B5[label="B"]

    C1[label="C"]
    C2[label="C"]
    C3[label="C"]
    C4[label="C"]
    C5[label="C"]
}

The above tree which represents all the permutations of "ABC" shows the path everytime we need to choose one. This tree is called **State Space Tree**. Here the leaves(last nodes) show the result.

Here we go back from one character to the previous one to check another character is available for permutation. This going back is known as **Back Tracking**.

With Backtracking we are exploring all the paths that are possible. This is known as **Brute Force**.

We can implement this Backtracking technique using recursion in the algorithm and code.

#### Code

void Permutation(char s[], int k)
{
    static int flag[20] = {0};
    static char result[20];

    if (s[k] == '\0')
    {
        result[k] = '\0';
        printf("%s ", result);
    }
    else
    {
        for (int i = 0; s[i] != '\0'; i++)
        {
            if (flag[i] == 0)
            {
                result[k] = s[i];
                flag[i] = 1;
                Permutation(s, k+1);
                A[i] = 0;
            }
        }
    }
}