Module 13: Strings (Data Structures)

Learning Objectives

By the end of this module, you will be able to:

• Understand strings and character arrays in C.
• Perform common string manipulation operations.
• Count character frequencies.
• Learn the basics of hashing for strings.
• Understand popular string matching algorithms.
• Implement KMP, Rabin-Karp, and Z Algorithm.
• Solve common string interview problems.

Introduction

Strings are one of the most frequently used data structures in programming.

Almost every software application works with strings:

• Search Engines
• Password Validation
• Text Editors
• Chat Applications
• Email Systems
• Compilers
• DNA Sequence Analysis
• Search Features

Many coding interviews include string problems because they test logic, array manipulation, and algorithmic thinking.

What is a String?

A string is a sequence of characters terminated by a null character ('\0').

Example

textCopy
1H e l l o \0

Memory Representation

textCopy
1Index : 0 1 2 3 4 5
2Value : H e l l o \0

The null character tells C where the string ends.

Character Arrays

Strings in C are stored as character arrays.

Example

cCopy
1char name[] = "Ankit";

Equivalent Representation

cCopy
1char name[] = {'A','n','k','i','t','\0'};

Example Program

cCopy
1#include <stdio.h>
2
3int main()
4{
5    char language[] = "Programming";
6
7    printf("%s", language);
8
9    return 0;
10}

Output

textCopy
1Programming

Reading Strings

Using scanf()

cCopy
1char name[30];
2
3scanf("%29s", name);

Limitation

scanf() stops reading when it encounters a space.

Input

textCopy
1Ankit Kushwaha

Output

textCopy
1Ankit

Using fgets()

cCopy
1char name[100];
2
3fgets(name, sizeof(name), stdin);

Advantages

• Reads spaces
• Prevents buffer overflow
• Safer than gets()

Common String Functions

Include

cCopy
1#include <string.h>

String Manipulation

Finding Length

cCopy
1#include <stdio.h>
2#include <string.h>
3
4int main()
5{
6    char str[] = "Computer";
7
8    printf("%lu", strlen(str));
9
10    return 0;
11}

Output

textCopy
18

Time Complexity

textCopy
1O(n)

Copying Strings

cCopy
1char source[] = "Hello";
2char destination[20];
3
4strcpy(destination, source);
5
6printf("%s", destination);

Output

textCopy
1Hello

Concatenating Strings

cCopy
1char first[30] = "Hello ";
2char second[] = "World";
3
4strcat(first, second);
5
6printf("%s", first);

Output

textCopy
1Hello World

Comparing Strings

cCopy
1char first[] = "Apple";
2char second[] = "Apple";
3
4if(strcmp(first, second) == 0)
5{
6    printf("Equal");
7}

Output

textCopy
1Equal

String Traversal

cCopy
1#include <stdio.h>
2
3int main()
4{
5    char str[] = "Coding";
6
7    for(int i = 0; str[i] != '\0'; i++)
8    {
9        printf("%c ", str[i]);
10    }
11
12    return 0;
13}

Output

textCopy
1C o d i n g

Time Complexity

textCopy
1O(n)

Frequency Count

Frequency count determines how many times each character appears.

Example

Input

textCopy
1banana

Output

textCopy
1a → 3
2b → 1
3n → 2

Program

cCopy
1#include <stdio.h>
2
3int main()
4{
5    char str[] = "banana";
6    int frequency[26] = {0};
7
8    for(int i = 0; str[i] != '\0'; i++)
9    {
10        frequency[str[i] - 'a']++;
11    }
12
13    for(int i = 0; i < 26; i++)
14    {
15        if(frequency[i] > 0)
16        {
17            printf("%c : %d\n", i + 'a', frequency[i]);
18        }
19    }
20
21    return 0;
22}

Time Complexity

textCopy
1O(n)

Hashing Basics

Hashing stores the frequency of characters for fast lookup.

Example

textCopy
1apple
2
3a → 1
4p → 2
5l → 1
6e → 1

Simple Hash Table

cCopy
1int hash[256] = {0};
2
3for(int i = 0; str[i] != '\0'; i++)
4{
5    hash[(unsigned char)str[i]]++;
6}

Applications

• Character counting
• Duplicate detection
• Anagram checking
• Fast searching

Time Complexity

textCopy
1O(n)

String Matching Algorithms

Searching for a pattern inside a large string is a common problem.

Example

Text

textCopy
1Programming in C Language

Pattern

textCopy
1Language

Naive Search checks every position and has a worst-case complexity of O(n × m), where:

• n = length of the text
• m = length of the pattern

Advanced algorithms improve efficiency.

KMP (Knuth-Morris-Pratt) Algorithm

KMP searches for a pattern without rechecking previously matched characters.

Idea

• Preprocess the pattern.
• Build an LPS (Longest Prefix Suffix) array.
• Skip unnecessary comparisons.

Example

textCopy
1Text
2
3ABABDABACDABABCABAB
4
5Pattern
6
7ABABCABAB

Time Complexity

textCopy
1Searching  : O(n)
2
3Preprocessing : O(m)
4
5Overall : O(n + m)

Advantages

• Fast
• Efficient
• Avoids repeated comparisons

Applications

• Text editors
• Search engines
• DNA matching

Rabin-Karp Algorithm

Rabin-Karp uses hash values instead of comparing every character.

Idea

• Compute the hash of the pattern.
• Compute the hash of each window in the text.
• Compare hashes first.
• If hashes match, verify the characters.

Example

textCopy
1Text
2
3ABCDEABCDE
4
5Pattern
6
7BCD

Time Complexity

textCopy
1Average : O(n + m)
2
3Worst : O(n × m)

Advantages

• Excellent for multiple pattern searches
• Efficient rolling hash

Applications

• Plagiarism detection
• Virus scanning
• Document searching

Z Algorithm

The Z Algorithm computes a Z-array, where each position stores the length of the longest substring starting from that position that matches the prefix of the string.

Example

textCopy
1String
2
3aabcaabxaaaz

Time Complexity

textCopy
1O(n)

Advantages

• Linear-time pattern matching
• Useful in competitive programming
• Efficient for prefix-related problems

Applications

• Pattern matching
• String compression
• DNA sequence analysis

Comparison of String Matching Algorithms

Practice Project 1: Reverse String

cCopy
1#include <stdio.h>
2#include <string.h>
3
4int main()
5{
6    char str[100];
7
8    printf("Enter a string: ");
9    fgets(str, sizeof(str), stdin);
10
11    int length = strlen(str);
12
13    if(length > 0 && str[length - 1] == '\n')
14    {
15        str[--length] = '\0';
16    }
17
18    for(int i = length - 1; i >= 0; i--)
19    {
20        printf("%c", str[i]);
21    }
22
23    return 0;
24}

Practice Project 2: Palindrome

cCopy
1#include <stdio.h>
2#include <string.h>
3
4int main()
5{
6    char str[100];
7
8    printf("Enter a string: ");
9    scanf("%99s", str);
10
11    int left = 0;
12    int right = strlen(str) - 1;
13
14    while(left < right)
15    {
16        if(str[left] != str[right])
17        {
18            printf("Not Palindrome");
19            return 0;
20        }
21
22        left++;
23        right--;
24    }
25
26    printf("Palindrome");
27
28    return 0;
29}

Time Complexity

textCopy
1O(n)

Practice Project 3: Anagram Checker

Two strings are anagrams if they contain the same characters with the same frequencies.

Example

textCopy
1listen
2
3silent

Program

cCopy
1#include <stdio.h>
2#include <string.h>
3
4int main()
5{
6    char first[100];
7    char second[100];
8
9    int frequency[256] = {0};
10
11    scanf("%99s", first);
12    scanf("%99s", second);
13
14    if(strlen(first) != strlen(second))
15    {
16        printf("Not Anagram");
17        return 0;
18    }
19
20    for(int i = 0; first[i] != '\0'; i++)
21    {
22        frequency[(unsigned char)first[i]]++;
23        frequency[(unsigned char)second[i]]--;
24    }
25
26    for(int i = 0; i < 256; i++)
27    {
28        if(frequency[i] != 0)
29        {
30            printf("Not Anagram");
31            return 0;
32        }
33    }
34
35    printf("Anagram");
36
37    return 0;
38}

Time Complexity

textCopy
1O(n)

Practice Project 4: Longest Common Prefix

Given

textCopy
1flower
2
3flow
4
5flight

Output

textCopy
1fl

Program

cCopy
1#include <stdio.h>
2#include <string.h>
3
4int main()
5{
6    char words[][20] = {"flower", "flow", "flight"};
7    int count = 3;
8
9    for(int i = 0; words[0][i] != '\0'; i++)
10    {
11        char current = words[0][i];
12
13        for(int j = 1; j < count; j++)
14        {
15            if(words[j][i] != current)
16            {
17                return 0;
18            }
19        }
20
21        printf("%c", current);
22    }
23
24    return 0;
25}

Time Complexity

textCopy
1O(n × m)

Where:

• n = number of strings
• m = length of the shortest string

Common Mistakes to Avoid

• Forgetting the null character ('\0') at the end of a string.
• Using gets() instead of the safer fgets().
• Accessing characters beyond the string length.
• Comparing strings with == instead of strcmp().
• Forgetting to allocate enough memory for the destination string before using strcpy() or strcat().
• Using Binary Search concepts on unsorted string data without proper preprocessing.

Best Practices

• Use fgets() for reading strings that may contain spaces.
• Include <string.h> when using standard string functions.
• Always validate string lengths before copying or concatenating.
• Prefer frequency arrays or hashing for character-count problems.
• Use KMP, Rabin-Karp, or the Z Algorithm for efficient pattern matching in large texts.
• Analyze both time and space complexity when choosing a string algorithm.

Module Summary

In this module, you learned:

• How strings are represented as character arrays in C.
• Common string manipulation functions such as strlen(), strcpy(), strcat(), and strcmp().
• How to traverse strings and count character frequencies.
• The basics of hashing for string processing.
• Advanced string matching algorithms including KMP, Rabin-Karp, and the Z Algorithm.
• How to solve common interview problems such as reversing a string, checking for palindromes, validating anagrams, and finding the longest common prefix.

After completing this module, you'll be ready to learn Linked Lists, where you'll explore dynamic memory allocation, node structures, singly and doubly linked lists, circular linked lists, and efficient insertion, deletion, and traversal operations.