Ruby String Strategies.md

Ruby String Problems Guide

Core Patterns

1. Character Frequency Pattern

def char_frequency(str)
  str.chars.each_with_object(Hash.new(0)) { |char, freq| freq[char] += 1 }
end

Use for:

• Finding first non-repeating character
• Finding most common character
• Character counting problems

2. Sliding Window Pattern

def sliding_window_template(str)
  last_seen = {}
  start = 0
  
  str.chars.each_with_index do |char, i|
    # Update window
    if need_to_shrink_window?(last_seen, char)
      start = find_new_start(last_seen, start)
    end
    
    # Update state
    last_seen[char] = i
    
    # Calculate current window properties
    curr_length = i - start + 1
  end
end

Use for:

• Finding longest substring with unique characters
• Finding substring with specific properties
• Window-based pattern matching

3. Two-Pointer Pattern

def two_pointer_template(str)
  left = 0
  right = str.length - 1
  
  while left < right
    # Process characters at left and right
    # Move pointers based on conditions
    left += 1
    right -= 1
  end
end

Use for:

• Palindrome checking
• Reversing strings
• Finding pairs

Example Problems

Problem 1: Longest Unique Substring

Find longest substring without repeating characters.

def longest_unique_substring(str)
  last_seen = {}
  max_length = 0
  start = 0
  max_substring = ""

  str.chars.each_with_index do |char, i|
    if last_seen[char] && last_seen[char] >= start
      start = last_seen[char] + 1
    end
    last_seen[char] = i
    curr_length = i - start + 1
    if curr_length > max_length
      max_length = curr_length
      max_substring = str[start..i]
    end
  end
  max_substring
end

Key concepts:

• Track last seen position of each character
• Move window start when finding repeats
• Calculate length using 0-based indexing (i - start + 1)

Time Complexity Tips

• Hash lookups are O(1)
• String slicing str[start..i] is O(n)
• Using chars.each_with_index is O(n)

Common Edge Cases

• Empty string
• Single character
• All same characters ("aaaa")
• No repeating characters ("abcd")
• Multiple equal-length answers