Implement string and basic ML algorithms

You are given three implementation tasks that mix algorithms and basic machine learning models.

---

Task 1: Longest substring with all distinct characters

Given a string s consisting of ASCII characters, find the length of the longest contiguous substring in which all characters are distinct (no character appears more than once within that substring).

• Input: a single string s.
• Output: an integer representing the maximum length of any substring of s that has all unique characters.

Example:

• s = abcabcbb → the answer is 3 (one such substring is abc).
• s = bbbbb → the answer is 1 (any single b).
• s = "" (empty string) → the answer is 0.

Constraints (typical):

• 0 <= len(s) <= 10^5
• Expected time: O(n) where n = len(s)
• Expected extra space: O(min(n, alphabet_size))

Implement a function with a signature similar to:

• int longestDistinctSubstringLength(const string& s) (C++), or
• int longest_distinct_substring_length(string s) (Python-style pseudocode).

---

Task 2: Implement binary logistic regression from scratch

Implement a binary logistic regression classifier without using any machine learning libraries.

Design a class LogisticRegression that supports:

• Constructor: takes at least:

  • learning_rate: float
  • num_iterations: int

• fit(X, y):

  • X is an n x d numeric matrix of features (e.g., list of length n, each element a length-d list of floats).
  • y is a length-n list/array of labels, each label is either 0 or 1.
  • Initialize weights and bias (e.g., to zeros).
  • Train using batch gradient descent to minimize the logistic (cross-entropy) loss:
    • Model: for each sample i, compute z_i = w · x_i + b, then probability of class 1 is p_i = sigmoid(z_i) = 1 / (1 + exp(-z_i)).
    • Loss over the dataset:

$L(w, b) = -\frac{1}{n} \sum_{i=1}^n \Bigl( y_i \log p_i + (1 - y_i) \log(1 - p_i) \Bigr).$

- Update `w` and `b` with gradient descent for `num_iterations` steps.

• No regularization is required.

• predict_proba(X):

  • Given a feature matrix X, return a list/array of predicted probabilities p_i for class 1 for each row.

• predict(X):

  • Given X, first compute probabilities with predict_proba, then convert to labels 0 or 1 using threshold 0.5.

Constraints (typical):

• n (number of samples) up to about 10^4.
• d (number of features) up to about 10^2.
• Number of iterations up to around 10^4.

You may implement in any language, but do not use built-in ML training utilities.

---

Task 3: Implement a multinomial Naive Bayes text classifier

Implement a multinomial Naive Bayes classifier for text classification.

Assume:

• Training data: docs_train, a list of documents, where each document is represented as a list of token strings, e.g. [["this", "movie", "is", "great"], ["awful", "film"], ...].
• Training labels: y_train, a list of integers where y_train[i] is the class index for docs_train[i] (values in {0, 1, ..., C-1}).
• Test data: docs_test, same format as docs_train but without labels.

Design a class NaiveBayes that supports:

• fit(docs_train, y_train):
  • Build a vocabulary of all tokens seen in docs_train.
  • Let C be the number of classes.
  • Estimate class prior probabilities:

$P(y = c) = \frac{\text{count of training docs with label } c}{\text{total number of docs}}.$

• For each class c and token w in the vocabulary, estimate conditional probabilities with Laplace smoothing (add-one smoothing):

$P(w \mid y = c) = \frac{\text{total count of token } w \text{ in class } c + 1}{\text{total token count in class } c + V},$

where `V` is the vocabulary size.

• Store log probabilities (log P(y = c) and log P(w | y = c)) to avoid underflow.

• predict(docs_test):

  • For each document, treat it as a bag of words.
  • For each class c, compute the log posterior up to a constant:

$\log P(y = c \mid \text{doc}) \propto \log P(y = c) + \sum_{w \in \text{doc}} \text{count}(w \text{ in doc}) \cdot \log P(w \mid y = c).$

• Predict the class c with the highest log score.
• Ignore tokens not in the training vocabulary (or handle them with an appropriate strategy such as skipping them).

Constraints (typical):

• Number of documents up to a few 10^4.
• Vocabulary size up to a few 10^4.
• Must be efficient in both time and memory.

Focus on correctly implementing the core training (fit) and prediction (predict) logic; you do not need to handle file I/O or text preprocessing (assume tokenization is already done).