Perfect ⚡ — You’ve conquered Day 1 (internals + basics) and Day 2 (algorithmic patterns).
Now it’s time for the grand finale — Day 3, where we’ll handle advanced string algorithms, sliding window logic, and numeric string processing.
This final day connects everything you’ve learned into high-performance interview-level mastery.
🚀 DAY 3 – Advanced String Algorithms, Sliding Windows & Numeric Logic
🎯 Goal
By the end of Day 3, you’ll:
- Implement sliding window–based substring algorithms
- Master number-string conversions (
add_binary,multiply_strings,int↔roman) - Build your own String Toolkit Module
- Understand how Python handles these under the hood
🧠 PART 1 – Substring Search & Sliding Window
Sliding window = one of the most powerful patterns for string problems.
🔹 1️⃣ Implement strStr() (Manual Substring Search)
👉 Pattern: Brute-force substring scan.
def str_str(haystack: str, needle: str) -> int:
if needle == "":
return 0
n, m = len(haystack), len(needle)
for i in range(n - m + 1):
if haystack[i:i+m] == needle:
return i
return -1
print(str_str("hello", "ll")) # 2
🔍 Behind the scenes, Python’s
find()uses optimized C algorithms (like the Two-Way algorithm, faster than naive search).
🔹 2️⃣ Longest Substring Without Repeating Characters
👉 Pattern: Sliding window + last seen index.
def length_of_longest_substring(s: str) -> int:
last_seen = {}
left = 0
best = 0
for right, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= left:
left = last_seen[ch] + 1
last_seen[ch] = right
best = max(best, right - left + 1)
return best
print(length_of_longest_substring("abcabcbb")) # 3 ("abc")
🧩 Pattern:
Expand window → detect violation (repeated char) → shrink from left.
🔹 3️⃣ Longest Substring with At Most K Distinct Characters
👉 Pattern: Sliding window + frequency map.
from collections import Counter
def longest_substring_k_distinct(s: str, k: int) -> int:
freq = Counter()
left = best = 0
for right, ch in enumerate(s):
freq[ch] += 1
while len(freq) > k:
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_substring_k_distinct("eceba", 2)) # 3 ("ece")
🔹 4️⃣ Minimum Window Substring (LeetCode #76)
👉 Pattern: Keep a window that contains all chars of another string.
from collections import Counter
def min_window(s: str, t: str) -> str:
if not s or not t:
return ""
need = Counter(t)
missing = len(t)
left = start = end = 0
for right, ch in enumerate(s, 1):
if need[ch] > 0:
missing -= 1
need[ch] -= 1
while missing == 0:
if end == 0 or right - left < end - start:
start, end = left, right
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return s[start:end]
print(min_window("ADOBECODEBANC", "ABC")) # "BANC"
🧠 Summary – Sliding Window Family
| Problem | Window Invariant | Example |
|---|---|---|
| Longest substring w/o repeat | No duplicate chars | "abcabcbb" |
| Longest substring ≤ K distinct | ≤ K unique chars | "eceba" |
| Minimum window substring | Contains all target chars | "ADOBECODEBANC" |
🪄 Key Pattern Rule:
Expand window → check violation → shrink window.
⚙️ PART 2 – Numeric String Operations
🔹 5️⃣ Add Two Binary Strings
def add_binary(a: str, b: str) -> str:
i, j = len(a) - 1, len(b) - 1
carry = 0
result = []
while i >= 0 or j >= 0 or carry:
bit_a = int(a[i]) if i >= 0 else 0
bit_b = int(b[j]) if j >= 0 else 0
total = bit_a + bit_b + carry
result.append(str(total % 2))
carry = total // 2
i -= 1
j -= 1
return "".join(reversed(result))
print(add_binary("11", "1")) # "100"
🧩 Concept: Manual binary addition — emulate bit-level logic.
🔹 6️⃣ Multiply Two Large Numbers (as Strings)
👉 Pattern: Simulate elementary school multiplication.
def multiply_strings(num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
m, n = len(num1), len(num2)
res = [0] * (m + n)
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
mul = (ord(num1[i]) - 48) * (ord(num2[j]) - 48)
total = mul + res[i + j + 1]
res[i + j + 1] = total % 10
res[i + j] += total // 10
# remove leading zeros
i = 0
while i < len(res) and res[i] == 0:
i += 1
return "".join(map(str, res[i:]))
print(multiply_strings("123", "456")) # "56088"
🔹 7️⃣ Integer to Roman
def int_to_roman(num: int) -> str:
values = [
(1000, "M"), (900, "CM"),
(500, "D"), (400, "CD"),
(100, "C"), (90, "XC"),
(50, "L"), (40, "XL"),
(10, "X"), (9, "IX"),
(5, "V"), (4, "IV"),
(1, "I"),
]
res = []
for val, sym in values:
while num >= val:
num -= val
res.append(sym)
return "".join(res)
print(int_to_roman(1994)) # "MCMXCIV"
🔹 8️⃣ Roman to Integer
def roman_to_int(s: str) -> int:
values = {
"I": 1, "V": 5, "X": 10, "L": 50,
"C": 100, "D": 500, "M": 1000
}
total = 0
i = 0
while i < len(s):
if i + 1 < len(s) and values[s[i]] < values[s[i + 1]]:
total += values[s[i + 1]] - values[s[i]]
i += 2
else:
total += values[s[i]]
i += 1
return total
print(roman_to_int("MCMXCIV")) # 1994
🔹 9️⃣ Basic Calculator (only +, -, (, ))
👉 Pattern: Stack to handle nested parentheses and cumulative signs.
def basic_calculator(expr: str) -> int:
stack = [1] # current sign context
sign = 1
result = 0
i = 0
n = len(expr)
while i < n:
ch = expr[i]
if ch.isdigit():
num = 0
while i < n and expr[i].isdigit():
num = num * 10 + int(expr[i])
i += 1
result += sign * num
continue
elif ch == '+':
sign = stack[-1]
elif ch == '-':
sign = -stack[-1]
elif ch == '(':
stack.append(sign)
elif ch == ')':
stack.pop()
i += 1
return result
print(basic_calculator("(1+(4+5+2)-3)+(6+8)")) # 23
🧩 PART 3 – Build Your Own String Toolkit
Let’s create a reusable module to consolidate all your functions:
# string_utils.py
def reverse_string(s): ...
def is_palindrome(s): ...
def compress_string(s): ...
def decode_string(s): ...
def add_binary(a, b): ...
def multiply_strings(a, b): ...
Then test it interactively:
from string_utils import *
print(reverse_string("Python"))
print(add_binary("101", "11"))
print(is_palindrome("RaceCar"))
This practice reinforces modular thinking, crucial for production-level code.
🧮 PART 4 – Practice Extensions (Optional Challenges)
- 🧠 Implement KMP substring search (O(n + m)) — advanced string matching.
- ⚙️ Add support for
*and/in the calculator (operator precedence). - 🔤 Write
evaluate_expression("3[a2[b]]") → abbabbabb. - 🔁 Build
convert_to_base(num: int, base: int)that returns string for any base (2–36). - 🧩 Implement
is_valid_parentheses(s)using stack (just brackets).
📘 Day 3 Summary
| Concept | Key Takeaways |
|---|---|
| Sliding Window | Dynamic range problems (expand–shrink logic) |
| Substring Search | Brute-force vs optimized pattern matching |
| Numeric Strings | Manual digit-by-digit computation |
| Roman ↔ Integer | Sequential + subtraction handling |
| Basic Calculator | Stack-based parsing & sign propagation |
| Modularization | Wrap all reusable string logic in one file |
🧠 End-of-Day Reflection Questions
- How does sliding window differ from two-pointer logic?
- Why is
join()still used even in advanced string construction? - How would you extend the calculator to handle
*and/? - What are the performance benefits of KMP search over brute-force?
- Why are manual binary operations important for interview-level problems?
🏁 Completion Certificate (Mentally 🧠💪)
🎉 You now know:
- Internals: Encoding, memory, immutability, interning.
- Patterns: Counter, stack, two pointers, sliding window.
- Advanced Logic: Substring search, binary/roman arithmetic.
- Production Skills: Modular, testable string utilities.
You’ve achieved full String Mastery in Python, from CPython internals to LeetCode level 🚀
Would you like me to now:
- 📓 Generate a full “Deep Python Strings in 3 Days.ipynb” Jupyter Notebook — with Day 1–3 markdown explanations, hints, and runnable code blocks,
or - 🧱 Package it as a Python project folder (with
/day1.py,/day2.py,/day3.py, and/string_utils.py) ready to open in VS Code?
