leetcode

commit 5501e17242ca51209b6971c6f2ce413240775406
parent 9b874847b53b83131aa0626abe48cfd4abd3bfc7
Author: Jack Sangdahl <jack@pngu.org>
Date:   Wed, 11 Feb 2026 21:12:06 -0700

3713. longest balanced substring 1

Diffstat:
A
longest_balance_substr1.c
 | 
40
++++++++++++++++++++++++++++++++++++++++
A
longest_balance_substr1.py
 | 
40
++++++++++++++++++++++++++++++++++++++++

2 files changed, 80 insertions(+), 0 deletions(-)
diff --git a/longest_balance_substr1.c b/longest_balance_substr1.c
@@ -0,0 +1,40 @@
+// 3713. Longest Balanced Substring I
+#include "leetcode.h"
+
+/*
+ * you are given a string 's' consisting of lowercase english letters. a
+ * substring of 's' is called balanced if all distinct characters in the
+ * substring appear the same number of times. return the length of the longest
+ * balanced substring of 's'.
+ */
+
+int longestBalanced(char *s) {
+  int n = strlen(s), ans = 0;
+  for (int i = 0; i < n; i++) {
+    int freq[26] = {0}, max = 0, cnt = 0;
+    for (int j = i; j < n; j++) {
+      int idx = s[j] - 'a';
+      if (!freq[idx])
+        cnt++;
+      freq[idx]++;
+      max = fmax(max, freq[idx]);
+      int curr = j - i + 1;
+      if (max * cnt == curr)
+        ans = fmax(ans, curr);
+    }
+  }
+  return ans;
+}
+
+int main() {
+  char *s1 = "abbac", *s2 = "zzabccy", *s3 = "aba";
+  int r1 = longestBalanced(s1);
+  int r2 = longestBalanced(s2);
+  int r3 = longestBalanced(s3);
+  printf("%d\n", r1); // expect: 4
+  assert(r1 == 4);
+  printf("%d\n", r2); // expect: 4
+  assert(r2 == 4);
+  printf("%d\n", r3); // expect: 2
+  assert(r3 == 2);
+}
diff --git a/longest_balance_substr1.py b/longest_balance_substr1.py
@@ -0,0 +1,40 @@
+# 3713. Longest Balanced Substring I
+
+"""
+you are given a string 's' consisting of lowercase english letters. a
+substring of 's' is called balanced if all distinct characters in the
+substring appear the same number of times. return the length of the longest
+balanced substring of 's'.
+"""
+
+
+class Solution(object):
+    def longestBalanced(self, s):
+        """
+        :type s: str
+        :rtype: int
+        """
+        n, ans = len(s), 0
+        s = [ord(char) - ord("a") for char in s]
+        for i in range(n):
+            if n - i <= ans:
+                break
+            freq = [0] * 26
+            unique = max_freq = 0
+            for j in range(i, n):
+                idx = s[j]
+                unique += freq[idx] == 0
+                freq[idx] += 1
+                if freq[idx] > max_freq:
+                    max_freq = freq[idx]
+                curr = j - i + 1
+                if unique * max_freq == curr and curr > ans:
+                    ans = curr
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.longestBalanced(s="abbac"))
+    print(obj.longestBalanced(s="zzabccy"))
+    print(obj.longestBalanced(s="aba"))