Day 5 of the 100 Days DSA Challenge: Strings Advanced

Welcome to Day 5 of the 100 Days DSA (Data Structures and Algorithms) Challenge! Today, we’ll dive deeper into advanced string manipulations. Strings are a fundamental part of programming, and mastering these advanced operations will enhance your problem-solving skills.

1. Write a Program to Check if Two Strings are Anagrams

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Placeholder for Code Example:

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool areAnagrams(char str1[], char str2[]) {
    int count[256] = {0};
    if (strlen(str1) != strlen(str2)) {
        return false;
    }
    for (int i = 0; str1[i] && str2[i]; i++) {
        count[(unsigned char)str1[i]]++;
        count[(unsigned char)str2[i]]--;
    }
    for (int i = 0; i < 256; i++) {
        if (count[i] != 0) {
            return false;
        }
    }
    return true;
}
int main() {
    char str1[] = "listen";
    char str2[] = "silent";
    if (areAnagrams(str1, str2)) {
        printf("The strings are anagrams.\n");
    } else {
        printf("The strings are not anagrams.\n");
    }
    return 0;
}

2. Solve the Problem of Finding the First Non-Repeating Character in a String

Finding the first non-repeating character helps in identifying unique elements within a string, which is a common problem in text processing.

Placeholder for Code Example:

#include <stdio.h>
#include <string.h>
#include <limits.h>

char firstNonRepeatingChar(char str[]) {
    int count[256] = {0};
    int index[256];
    for (int i = 0; str[i]; i++) {
        count[(unsigned char)str[i]]++;
        if (count[(unsigned char)str[i]] == 1) {
            index[(unsigned char)str[i]] = i;
        } else {
            index[(unsigned char)str[i]] = INT_MAX;
        }
    }
    int minIndex = INT_MAX;
    for (int i = 0; i < 256; i++) {
        if (count[i] == 1 && index[i] < minIndex) {
            minIndex = index[i];
        }
    }
    return minIndex == INT_MAX ? '\0' : str[minIndex];
}
int main() {
    char str[] = "swiss";
    char result = firstNonRepeatingChar(str);
    if (result != '\0') {
        printf("First non-repeating character: %c\n", result);
    } else {
        printf("No non-repeating character found.\n");
    }
    return 0;
}

3. Write a Function to Find All Substrings of a String

Substrings are contiguous sequences of characters within a string, and finding all substrings is useful in various text processing and searching algorithms.

Placeholder for Code Example:

#include <stdio.h>
#include <string.h>

void printSubstrings(char str[]) {
    int n = strlen(str);
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            for (int k = i; k <= j; k++) {
                printf("%c", str[k]);
            }
            printf("\n");
        }
    }
}
int main() {
    char str[] = "ABCD";
    printSubstrings(str);
    return 0;
}

4. Implement a Program to Replace Spaces in a String with a Special Character (e.g., %20)

Replacing spaces with a special character is a common task in URL encoding and text formatting.

Placeholder for Code Example:

#include <stdio.h>
#include <string.h>

void replaceSpaces(char str[], char replacement[]) {
    int length = strlen(str);
    int replacementLength = strlen(replacement);
    int spaceCount = 0;
    for (int i = 0; str[i]; i++) {
        if (str[i] == ' ') {
            spaceCount++;
        }
    }
    int newLength = length + spaceCount * (replacementLength - 1);
    str[newLength] = '\0';
    for (int i = length - 1; i >= 0; i--) {
        if (str[i] == ' ') {
            newLength -= replacementLength;
            memcpy(&str[newLength], replacement, replacementLength);
        } else {
            str[--newLength] = str[i];
        }
    }
}
int main() {
    char str[100] = "Hello world, Program four.";
    replaceSpaces(str, "%20");
    printf("String after replacing spaces: %s\n", str);
    return 0;
}

5. Solve the "Longest Common Prefix" Problem for an Array of Strings

Finding the longest common prefix is useful in various applications, such as auto-complete features and DNA sequence analysis.

Placeholder for Code Example:

#include <stdio.h>
#include <string.h>

char* longestCommonPrefix(char arr[][100], int n) {
    static char result[100];
    strcpy(result, arr[0]);
    for (int i = 1; i < n; i++) {
        int j = 0;
        while (j < strlen(result) && j < strlen(arr[i]) && result[j] == arr[i][j]) {
            j++;
        }
        result[j] = '\0';
    }
    return result;
}
int main() {
    char arr[3][100] = {"flower", "flow", "flight"};
    char* result = longestCommonPrefix(arr, 3);
    printf("Longest common prefix: %s\n", result);
    return 0;
}

Conclusion

Today’s challenges are designed to deepen your understanding of advanced string operations. By tackling these exercises, you’ll be better equipped to handle complex text processing tasks in your coding journey. Keep pushing forward, and see you tomorrow for Day 6 of the 100 Days DSA Challenge!