Balanced Package Sequence — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Two Pointers and solve the Balanced Package Sequence problem optimally.
O(n)O(n)Problem Description
Given a string s composed exclusively of the characters ‘L’ (large package) and ‘S’ (small package), determine the maximum length of a contiguous substring that satisfies two conditions: (1) the number of ‘L’ characters equals the number of ‘S’ characters, and (2) the first and last characters of the substring are identical. If no such substring exists, return 0. The algorithm must run efficiently for large inputs.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Balanced Package Sequence"
WHY DOES IT MATTER?
Balancing two types of items while preserving endpoint constraints appears in load‑balancing, memory allocation, and even DNA sequence analysis. Mastering this pattern teaches you to combine prefix‑sum tricks with additional state (here, endpoint character) to meet compound constraints.
OPTIMIZATION CHALLENGE
The breakthrough is realizing that equal counts translate to equal prefix differences, allowing O(1) lookup of matching starts via a hash map keyed by (character, prefixDiff). This eliminates the need to examine every pair of indices.
REAL-WORLD CONNECTION
Imagine a distributed log where ‘L’ entries are large payloads and ‘S’ are small acknowledgments. You want the longest contiguous segment where the total payload size equals total acknowledgment size and the segment starts and ends with the same service node – a classic consistency checkpoint problem.
During the interview, compute the prefix diff on the fly, update the map only when you see a character for the first time with that diff, and immediately check the current index against the stored start – a single pass, no back‑tracking.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem reduces to finding the longest subarray with zero net balance between two symbols while also enforcing that the subarray’s endpoints are the same symbol. By mapping ‘L’ to +1 and ‘S’ to –1, the prefix sum (or difference) array captures the cumulative imbalance. A substring i..j has equal numbers of ‘L’ and ‘S’ exactly when prefixDiff[j+1]==prefixDiff[i]. The additional endpoint constraint means we can only pair positions i and j that share the same character. A naïve O(n²) scan checks every pair, which explodes for strings of length 10⁵ or more. The optimal paradigm combines prefix‑sum hashing with a two‑pointer‑like lookup: for each character type we store the earliest index where a particular prefix difference occurred. When we reach a new index, we instantly know the farthest matching start that satisfies both balance and endpoint equality, yielding a linear‑time solution.
Interview Questions on This Problem
Q1How would you modify the solution if the substring must start and end with different characters instead of the same?
Maintain two hash maps per character: one for earliest occurrence of each prefix diff when the character is ‘L’, another for ‘S’. When at index j, look up the earliest index i with the opposite character but the same prefix diff, then compute length. The rest of the algorithm stays identical.
Q2Can this problem be solved using a sliding window technique? Why or why not?
A pure sliding‑window fails because the balance condition is not monotonic; expanding or shrinking the window can both increase and decrease the net difference, so we cannot guarantee a single moving window will capture the optimum. Prefix‑sum hashing is required to jump directly to matching balances.
Q3What is the time‑space trade‑off if you restrict yourself to O(1) extra space?
Without auxiliary hash maps you would need to recompute balances for every possible start, reverting to O(n²) time. Thus achieving O(1) space forces a quadratic‑time algorithm, which is unacceptable for large inputs.
Examples
Input
LLSSLS
Output
4
Explanation: All substrings are examined. The substring from index 1 to 4 (“LSSL”) contains two ‘L’ and two ‘S’, and both its first and last characters are ‘L’. Its length 4 is the largest possible that meets the criteria.
Input
SSLLSSLL
Output
4
Explanation: Scanning the string reveals several balanced substrings. The segment from index 1 to 4 (“SLLS”) has equal counts (2 ‘L’, 2 ‘S’) and starts and ends with ‘S’, giving length 4. No longer balanced substring also starts and ends with the same character, so the answer is 4.
Input
LSLSLS
Output
0
Explanation: Every balanced substring (equal numbers of ‘L’ and ‘S’) in this string begins with a different character than it ends. Consequently, no substring fulfills both requirements, and the result is 0.
Constraints
- 1 <= s.length <= 200000
- s[i] is either 'L' or 'S'
Optimal Approach & Strategy
Use a prefix‑difference map per character to instantly locate the farthest matching start with the same diff, achieving O(n) time.
Brute Force Approach
Check every possible substring, count ‘L’ and ‘S’, and verify the first and last characters – O(n²) time.
Code Solutions
function balancedPackageSequence(s) {
let max_length = 0;
for (let i = 0; i < s.length; i++) {
let l_count = 0;
let s_count = 0;
for (let j = i; j < s.length; j++) {
if (s[j] === 'L') l_count++;
else s_count++;
if (l_count === s_count && s[i] === s[j]) {
max_length = Math.max(max_length, j - i + 1);
}
}
}
return max_length;
}
const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
readline.question('Enter a string: ', s => {
const result = balancedPackageSequence(s);
console.log(`Result: ${result}`);
readline.close();
});
#include <iostream>
#include <string>
int balancedPackageSequence(std::string s) {
int max_length = 0;
for (int i = 0; i < s.size(); i++) {
int l_count = 0;
int s_count = 0;
for (int j = i; j < s.size(); j++) {
if (s[j] == 'L') l_count++;
else s_count++;
if (l_count == s_count && s[i] == s[j]) {
max_length = std::max(max_length, j - i + 1);
}
}
}
return max_length;
}
int main() {
std::string s;
std::cout << "Enter a string: ";
std::cin >> s;
int result = balancedPackageSequence(s);
std::cout << "Result: " << result << std::endl;
return 0;
}
import java.util.Scanner;
public class BalancedPackageSequence {
public static int balancedPackageSequence(String s) {
int max_length = 0;
for (int i = 0; i < s.length(); i++) {
int l_count = 0;
int s_count = 0;
for (int j = i; j < s.length(); j++) {
if (s.charAt(j) == 'L') l_count++;
else s_count++;
if (l_count == s_count && s.charAt(i) == s.charAt(j)) {
max_length = Math.max(max_length, j - i + 1);
}
}
}
return max_length;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter a string: ");
String s = scanner.nextLine();
int result = balancedPackageSequence(s);
System.out.println("Result: " + result);
scanner.close();
}
}
def balanced_package_sequence(s):
max_length = 0
for i in range(len(s)):
l_count = 0
s_count = 0
for j in range(i, len(s)):
if s[j] == 'L':
l_count += 1
else:
s_count += 1
if l_count == s_count and s[i] == s[j]:
max_length = max(max_length, j - i + 1)
return max_length
if __name__ == "__main__":
s = input("Enter a string: ")
result = balanced_package_sequence(s)
print("Result:", result)
function balancedPackageSequence(s) {
let max_length = 0;
for (let i = 0; i < s.length; i++) {
let l_count = 0;
let s_count = 0;
for (let j = i; j < s.length; j++) {
if (s[j] === 'L') l_count++;
else s_count++;
if (l_count === s_count && s[i] === s[j]) {
max_length = Math.max(max_length, j - i + 1);
}
}
}
return max_length;
}
const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
readline.question('Enter a string: ', s => {
const result = balancedPackageSequence(s);
console.log(`Result: ${result}`);
readline.close();
});
Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.