Longest Substring Without Repeating Characters - C Solution

1. Introduction

In this post, we explore a common problem in string processing - finding the longest substring without repeating characters in a given string. This problem is a good test of understanding how to manipulate and traverse strings while keeping track of characters efficiently.

Problem

Given a string s, the task is to find the length of the longest substring that does not have any repeating characters.

2. Solution Steps

1. Create a hash table or array to store the last index of each character encountered.

2. Initialize two pointers to define the current window of non-repeating characters.

3. Iterate through the string, expanding the window and updating the character's last index.

4. If a repeating character is found, move the start pointer to the right of the last occurrence of the repeated character.

5. Calculate the length of the current window at each step and update the maximum length found.

6. Return the maximum length after processing the entire string.

3. Code Program

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

// Function to find the length of the longest substring without repeating characters
int lengthOfLongestSubstring(char* s) {
    int lastIndex[256] = {-1}; // Initialize hash table for last indices
    int maxLength = 0;
    int start = 0; // Start index of current window

    for (int end = 0; s[end] != '\0'; end++) {
        if (lastIndex[s[end]] >= start) {
            start = lastIndex[s[end]] + 1;
        }
        lastIndex[s[end]] = end;
        maxLength = maxLength > end - start + 1 ? maxLength : end - start + 1;
    }

    return maxLength;
}

// Main function to test the lengthOfLongestSubstring function
int main() {
    char s1[] = "abcabcbb";
    printf("Longest Substring Without Repeating Characters (Example 1): %d\n", lengthOfLongestSubstring(s1));

    char s2[] = "bbbbb";
    printf("Longest Substring Without Repeating Characters (Example 2): %d\n", lengthOfLongestSubstring(s2));

    char s3[] = "pwwkew";
    printf("Longest Substring Without Repeating Characters (Example 3): %d\n", lengthOfLongestSubstring(s3));

    return 0;
}

Output:

Longest Substring Without Repeating Characters (Example 1): 3
Longest Substring Without Repeating Characters (Example 2): 1
Longest Substring Without Repeating Characters (Example 3): 3

Explanation:

1. Initialize a hash table to store the last index of each character.

2. Use a sliding window approach with start and end pointers.

3. Move end pointer through the string, updating the last index of each character.

4. If a repeat character is encountered, move the start pointer past the last occurrence.

5. Update maxLength with the length of the current window as needed.

6. After iterating through the string, return maxLength.

7. The main function tests the lengthOfLongestSubstring function with three examples and prints the results.