PROBLEM SOLVING - STRINGS IN C INTRODUCTION

String Basics in C

String Definition

A string in C is an array of characters terminated by a null character ('\0'). Key characteristics:

  • Null-terminated - Must end with '\0'
  • Character array - Implemented as arrays of type char
  • Mutable - Can be modified character by character
// Syntax:
char string_name[size];

String Applications

Strings are fundamental in C programming with various applications:

  • Text processing and manipulation
  • Input/output operations
  • File handling and parsing
  • Database operations
  • Network programming
  • Command-line arguments
  • Regular expressions

String Initialization

Strings can be initialized in several ways in C:

// Method 1: Initialize with string literal
char str1[] = "Hello";

// Method 2: Initialize character by character
char str2[6] = {'H', 'e', 'l', 'l', 'o', '\0'};

// Method 3: Initialize without size
char str3[] = {'H', 'e', 'l', 'l', 'o', '\0'};

// Method 4: Initialize with pointer
char *str4 = "Hello";  // String literal (read-only)

Common String Functions

C provides several built-in string functions in string.h:

  • strlen() - Returns length of string
  • strcpy() - Copies one string to another
  • strcat() - Concatenates two strings
  • strcmp() - Compares two strings
  • strstr() - Finds substring in string
  • strtok() - Tokenizes string

Accessing Strings

Elements in a string are accessed using their index:

char greeting[] = "Hello";

// Accessing elements
char first = greeting[0]; // 'H'
char third = greeting[2]; // 'l'

// Modifying elements
greeting[1] = 'a'; // Changes to "Hallo"

// Looping through string
for(int i = 0; greeting[i] != '\0'; i++) {
    printf("%c", greeting[i]);
}

String Input/Output

Basic string input/output operations:

// Input
char name[50];
printf("Enter your name: ");
scanf("%s", name);  // Reads until whitespace
// OR
fgets(name, sizeof(name), stdin);  // Reads entire line

// Output
printf("Hello, %s\n", name);
puts(name);  // Prints string with newline

PROBLEM SOLVING - STRINGS TRICKS

String Manipulation Approaches

# Technique Use Case Approach Complexity Examples
1 Two-Pointer Reverse string, check palindrome, or remove characters Use two pointers (start & end) to traverse from both ends O(n)
  • Reverse a string
  • Check palindrome
  • Remove duplicates
  • Valid palindrome
2 Sliding Window Find substrings with specific conditions Maintain a window (substring) and adjust size dynamically O(n)
  • Longest substring without repeating
  • Minimum window substring
  • Anagrams in a string
3 Pattern Matching Find patterns or substrings in text Use algorithms like KMP, Boyer-Moore, or Rabin-Karp O(n+m)
  • Find substring
  • Wildcard matching
  • Regular expressions
4 String Reversal Reverse entire string or portions Use two pointers or stack-based reversal O(n)
  • Reverse words in string
  • Reverse vowels
  • Reverse string II
5 Frequency Counting Count character occurrences or find duplicates Use hash map or array for character frequencies O(n)
  • First unique character
  • Anagram check
  • Isomorphic strings
6 String Tokenization Split string into tokens Use strtok() or manual delimiter tracking O(n)
  • Split string by delimiter
  • Count words
  • Reverse words
7 String Encoding Compress or encode strings Run-length encoding or other compression O(n)
  • Run-length encoding
  • String compression
  • URL encoding
8 String Manipulation Modify strings in-place Track positions and modify characters O(n) time O(1) space
  • Remove characters
  • Replace spaces
  • Remove duplicates

Common String Operations

String Length Without strlen() 
int length = 0;
while(str[length] != '\0') {
    length++;
}
printf("Length: %d", length);
Time Complexity: O(n)
String Copy Without strcpy() 
int i = 0;
while(src[i] != '\0') {
    dest[i] = src[i];
    i++;
}
dest[i] = '\0';
Time Complexity: O(n)
String Concatenation Without strcat() 
int i = 0, j = 0;
while(dest[i] != '\0') i++;
while(src[j] != '\0') {
    dest[i++] = src[j++];
}
dest[i] = '\0';
Time Complexity: O(n+m)
String Comparison Without strcmp() 
int i = 0;
while(str1[i] == str2[i]) {
    if(str1[i] == '\0') return 0;
    i++;
}
return str1[i] - str2[i];
Time Complexity: O(n)
Palindrome Check 
int left = 0, right = strlen(str) - 1;
while(left < right) {
    if(str[left++] != str[right--]) {
        printf("Not a palindrome");
        return;
    }
}
printf("Palindrome");
Time Complexity: O(n)
Count Vowels in String 
int count = 0;
for(int i = 0; str[i] != '\0'; i++) {
    char c = tolower(str[i]);
    if(c == 'a' || c == 'e' || c == 'i' || 
       c == 'o' || c == 'u') {
        count++;
    }
}
printf("Vowel count: %d", count);
Time Complexity: O(n)

Advanced String Techniques

# Technique Description Use Case
1 KMP Algorithm Pattern matching using prefix function to avoid unnecessary comparisons Efficient substring search
2 Boyer-Moore Pattern matching that skips sections of text using bad character rule Fast text search
3 Rabin-Karp Pattern matching using hashing to find exact matches Multiple pattern search
4 Trie (Prefix Tree) Tree-like data structure for efficient string storage and retrieval Autocomplete, dictionary
5 Suffix Array Sorted array of all suffixes of a string for efficient searching Genomics, text search
6 Run-Length Encoding Basic data compression that replaces repeated characters with counts Simple compression
7 Huffman Coding Optimal prefix coding for lossless data compression Text compression
8 Levenshtein Distance Measure of difference between two sequences (edit distance) Spell check, DNA analysis
9 String Hashing Convert strings to fixed-size values for quick comparison Password storage, deduplication
10 Regular Expressions Pattern matching using special syntax to match complex patterns Text validation, extraction
11 String Rotation Check if one string is rotation of another using concatenation String manipulation
12 Anagram Detection Check if two strings contain same characters in different order Word games, cryptography
13 String Encryption Techniques like Caesar cipher, Vigenère cipher for security Data security
14 Spell Checking Using algorithms like BK-tree or SymSpell for spelling correction Word processors
15 Unicode Handling Proper processing of multi-byte characters and encodings Internationalization
Related String Resources
Basic Programs
Interview Questions
MCQs
String Tricks