LeetCode 3714 | Longest Balanced Substring II | Java | Medium | Prefix Sum | CodeByTushu
Description: 🚀 Welcome Back to CodeByTushu!
In today’s video, we solve LeetCode 3714 — Longest Balanced Substring II using String, Hash Table, and Prefix Sum in Java.
We are given a string named s containing up to 100,000 characters, consisting only of the letters a, b, and c. We need to find the length of the longest substring where every distinct character appears the same number of times.
Since the alphabet contains only three characters, a balanced substring can contain one, two, or three distinct characters. We divide the problem into three cases. The first case involves one distinct character and can be solved by finding the longest continuous block of identical characters. The second case involves two distinct characters, where the third character is absent and the other two characters have equal frequencies. The third case involves all three characters appearing equally often.
For the two-character case, the excluded character acts as a delimiter. We split the string into segments and use a one-dimensional prefix difference to find the longest substring with equal character counts.
For the three-character case, we use a two-dimensional prefix balance state based on the difference between the counts of a and b, and the difference between the counts of b and c. By storing the earliest occurrence of each state using an efficient 64-bit encoding in a hash map, we can identify valid substrings in O(1) average lookup time. This approach achieves O(n) time complexity and O(n) auxiliary space, efficiently handling strings containing up to 100,000 characters.
🔥 Problem Highlights
✅ Divided the problem into cases with one, two, and three distinct characters
✅ Scanned consecutive character runs to solve the one-character case in O(n) time
✅ Used delimiter-based segment isolation for pairs of distinct characters
✅ Applied a two-dimensional prefix difference state for balancing three characters
✅ Used efficient 64-bit bitwise state encoding to avoid string key allocations
✅ Achieved O(n) time complexity and O(n) auxiliary space
⏱️ TIMESTAMPS
00:00 Intro
01:01 Problem Understanding and Constraints
02:01 Three Disjoint Categories and State Formulation
03:58 Three-Case Linear-Time Algorithmic Strategy
05:28 Java Code Walkthrough and Bit Packing
07:00 Execution and Test Cases Walkthrough
08:11 Time Complexity Analysis O(n)
09:05 Space Complexity Analysis O(n)
09:39 Outro and Wrap-up
📂 Problem Folder and Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/February/13-February/3714-Longest-Balanced-Substring-II
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/13-February/3714-Longest-Balanced-Substring-II/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/13-February/3714-Longest-Balanced-Substring-II/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/13-February/3714-Longest-Balanced-Substring-II/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/13-February/3714-Longest-Balanced-Substring-II/solution.js
🔗 LeetCode Source Code
📌 Add the link here
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Medium Problems
Java DSA Preparation
Prefix Sum State Encoding
Multi-Character Balance Invariants
Linear Time Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why can equal frequencies of a, b, and c be identified using a two-dimensional state containing the difference between the counts of a and b, and the difference between the counts of b and c?
1️⃣ Because both differences become zero when all three character counts are equal
2️⃣ Because prefix sums only work when the difference is strictly positive
3️⃣ Because the string length must always be a multiple of three
4️⃣ Because the character c always appears at least once in every substring
#LeetCode3714 #LeetCode #LongestBalancedSubstringII #Java #JavaDSA #String #PrefixSum #HashTable #DSA #CodingInterview #ProblemSolving #LeetCodeMedium #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
In today’s video, we solve LeetCode 3714 — Longest Balanced Substring II using String, Hash Table, and Prefix Sum in Java.
We are given a string named s containing up to 100,000 characters, consisting only of the letters a, b, and c. We need to find the length of the longest substring where every distinct character appears the same number of times.
Since the alphabet contains only three characters, a balanced substring can contain one, two, or three distinct characters. We divide the problem into three cases. The first case involves one distinct character and can be solved by finding the longest continuous block of identical characters. The second case involves two distinct characters, where the third character is absent and the other two characters have equal frequencies. The third case involves all three characters appearing equally often.
For the two-character case, the excluded character acts as a delimiter. We split the string into segments and use a one-dimensional prefix difference to find the longest substring with equal character counts.
For the three-character case, we use a two-dimensional prefix balance state based on the difference between the counts of a and b, and the difference between the counts of b and c. By storing the earliest occurrence of each state using an efficient 64-bit encoding in a hash map, we can identify valid substrings in O(1) average lookup time. This approach achieves O(n) time complexity and O(n) auxiliary space, efficiently handling strings containing up to 100,000 characters.
🔥 Problem Highlights
✅ Divided the problem into cases with one, two, and three distinct characters
✅ Scanned consecutive character runs to solve the one-character case in O(n) time
✅ Used delimiter-based segment isolation for pairs of distinct characters
✅ Applied a two-dimensional prefix difference state for balancing three characters
✅ Used efficient 64-bit bitwise state encoding to avoid string key allocations
✅ Achieved O(n) time complexity and O(n) auxiliary space
⏱️ TIMESTAMPS
00:00 Intro
01:01 Problem Understanding and Constraints
02:01 Three Disjoint Categories and State Formulation
03:58 Three-Case Linear-Time Algorithmic Strategy
05:28 Java Code Walkthrough and Bit Packing
07:00 Execution and Test Cases Walkthrough
08:11 Time Complexity Analysis O(n)
09:05 Space Complexity Analysis O(n)
09:39 Outro and Wrap-up
📂 Problem Folder and Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/February/13-February/3714-Longest-Balanced-Substring-II
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/13-February/3714-Longest-Balanced-Substring-II/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/13-February/3714-Longest-Balanced-Substring-II/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/13-February/3714-Longest-Balanced-Substring-II/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/February/13-February/3714-Longest-Balanced-Substring-II/solution.js
🔗 LeetCode Source Code
📌 Add the link here
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Medium Problems
Java DSA Preparation
Prefix Sum State Encoding
Multi-Character Balance Invariants
Linear Time Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why can equal frequencies of a, b, and c be identified using a two-dimensional state containing the difference between the counts of a and b, and the difference between the counts of b and c?
1️⃣ Because both differences become zero when all three character counts are equal
2️⃣ Because prefix sums only work when the difference is strictly positive
3️⃣ Because the string length must always be a multiple of three
4️⃣ Because the character c always appears at least once in every substring
#LeetCode3714 #LeetCode #LongestBalancedSubstringII #Java #JavaDSA #String #PrefixSum #HashTable #DSA #CodingInterview #ProblemSolving #LeetCodeMedium #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
