Overview

Strings are data structures comprised of a sequence of characters, Much like arrays, strings allow for efficient access to individual characters via indexing, making them remarkably similar to arrays in how they can be manipulated and accessed. Given this similarity, a solid understanding of arrays is beneficial as many of the same techniques and operations can directly apply to strings as well.

Important Techniques

➡️🪟 ➡️ Sliding window

This technique, as listed under arrays, utilizes a similar approach in string manipulation, so please refer back to that section if you need a fundamental overview of the sliding window concept. In the context of strings, the sliding window technique is particularly effective for solving problems that involve substrings, where the goal is to find or analyze substrings within a larger string based on specific criteria

Let’s go through this Example Problem: Longest Substring Without Repeating Characters

Problem: Longest Substring Without Repeating Characters

We are given a string s. The task is to find the length of the longest substring without repeating characters.

Brainstorming the Approach

1. Sliding Window Technique:
   • This problem is well-suited for the sliding window technique because we are looking for a contiguous substring.
   • The goal is to find the longest possible substring that does not contain any duplicate characters.
   • We maintain a sliding window that dynamically expands by adding characters from the right until we encounter a repeated character. When we do, we shrink the window from the left until there are no more duplicates.
2. Key Observations:
   • As we slide the window, we need a way to efficiently check for duplicates. This can be done using a set to track the characters in the current window.
   • If a duplicate character is found, we shrink the window from the left until the duplicate is removed, then continue expanding from the right.
   • We keep track of the maximum length of any valid window encountered.
3. Edge Cases:
   • If the string is empty, return 0.
   • If the string contains only one unique character repeated multiple times, the result should be 1.
   • Consider strings with mixed character types (letters, digits, symbols, spaces).

Pseudocode

• Initialize variables:
  • left to track the left boundary of the window.
  • char_set to keep track of the unique characters in the current window.
  • max_length to store the maximum length of a valid substring encountered.
• Loop through each character in the string using an index right for the right boundary of the window:
  • If the current character is already in char_set (i.e., a duplicate is found):
    • Shrink the window from the left by removing characters from char_set and incrementing left until the duplicate is removed.
  • Add the current character to char_set.
  • Update max_length to be the maximum of max_length and the current window length (right - left + 1).
• Return max_length after traversing the entire string.

Code Implementation

def lengthOfLongestSubstring(s):
    char_set = set()
    left = 0
    max_length = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)

    return max_length

Explanation of the Code

1. Initialization:
   • We initialize an empty set char_set to track the unique characters in the current window.
   • We set left to 0 to represent the left boundary of the window and max_length to 0 to keep track of the maximum length of valid substrings.