Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
You are given an array of strings arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters.
Return the maximum possible length of s.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All the valid concatenations are:
- ""
- "un"
- "iq"
- "ue"
- "uniq" ("un" + "iq")
- "ique" ("iq" + "ue")
Maximum length is 4.
Example 2:
Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible longest valid concatenations are "chaers" ("cha" + "ers") and "acters" ("act" + "ers").
Example 3:
Input: arr = ["abcdefghijklmnopqrstuvwxyz"] Output: 26 Explanation: The only string in arr has all 26 characters.
Constraints:
1 <= arr.length <= 161 <= arr[i].length <= 26arr[i] contains only lowercase English letters.Problem summary: You are given an array of strings arr. A string s is formed by the concatenation of a subsequence of arr that has unique characters. Return the maximum possible length of s. A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Backtracking · Bit Manipulation
["un","iq","ue"]
["cha","r","act","ers"]
["abcdefghijklmnopqrstuvwxyz"]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1239: Maximum Length of a Concatenated String with Unique Characters
class Solution {
public int maxLength(List<String> arr) {
List<Integer> s = new ArrayList<>();
s.add(0);
int ans = 0;
for (var t : arr) {
int x = 0;
for (char c : t.toCharArray()) {
int b = c - 'a';
if ((x >> b & 1) == 1) {
x = 0;
break;
}
x |= 1 << b;
}
if (x > 0) {
for (int i = s.size() - 1; i >= 0; --i) {
int y = s.get(i);
if ((x & y) == 0) {
s.add(x | y);
ans = Math.max(ans, Integer.bitCount(x | y));
}
}
}
}
return ans;
}
}
// Accepted solution for LeetCode #1239: Maximum Length of a Concatenated String with Unique Characters
func maxLength(arr []string) (ans int) {
s := []int{0}
for _, t := range arr {
x := 0
for _, c := range t {
b := int(c - 'a')
if (x>>b)&1 == 1 {
x = 0
break
}
x |= 1 << b
}
if x > 0 {
for i := len(s) - 1; i >= 0; i-- {
y := s[i]
if (x & y) == 0 {
s = append(s, x|y)
ans = max(ans, bits.OnesCount(uint(x|y)))
}
}
}
}
return ans
}
# Accepted solution for LeetCode #1239: Maximum Length of a Concatenated String with Unique Characters
class Solution:
def maxLength(self, arr: List[str]) -> int:
s = [0]
for t in arr:
x = 0
for b in map(lambda c: ord(c) - 97, t):
if x >> b & 1:
x = 0
break
x |= 1 << b
if x:
s.extend((x | y) for y in s if (x & y) == 0)
return max(x.bit_count() for x in s)
// Accepted solution for LeetCode #1239: Maximum Length of a Concatenated String with Unique Characters
struct Solution;
impl Solution {
fn max_length(arr: Vec<String>) -> i32 {
let arr: Vec<u32> = arr
.into_iter()
.filter_map(|s| {
let mut bitset = 0;
for b in s.bytes() {
let bit = 1 << (b - b'a');
if bitset & bit != 0 {
return None;
} else {
bitset |= bit
}
}
Some(bitset)
})
.collect();
let n = arr.len();
let mut res = 0;
Self::dfs(0, 0, &mut res, &arr, n);
res as i32
}
fn dfs(start: usize, cur: u32, max: &mut u32, arr: &[u32], n: usize) {
if start == n {
*max = (*max).max(cur.count_ones());
} else {
if arr[start] & cur == 0 {
Self::dfs(start + 1, cur | arr[start], max, arr, n);
}
Self::dfs(start + 1, cur, max, arr, n);
}
}
}
#[test]
fn test() {
let arr = vec_string!["un", "iq", "ue"];
let res = 4;
assert_eq!(Solution::max_length(arr), res);
let arr = vec_string!["cha", "r", "act", "ers"];
let res = 6;
assert_eq!(Solution::max_length(arr), res);
let arr = vec_string!["abcdefghijklmnopqrstuvwxyz"];
let res = 26;
assert_eq!(Solution::max_length(arr), res);
}
// Accepted solution for LeetCode #1239: Maximum Length of a Concatenated String with Unique Characters
function maxLength(arr: string[]): number {
const s: number[] = [0];
let ans = 0;
for (const t of arr) {
let x = 0;
for (const c of t) {
const b = c.charCodeAt(0) - 97;
if ((x >> b) & 1) {
x = 0;
break;
}
x |= 1 << b;
}
if (x > 0) {
for (let i = s.length - 1; ~i; --i) {
const y = s[i];
if ((x & y) === 0) {
s.push(x | y);
ans = Math.max(ans, bitCount(x | y));
}
}
}
}
return ans;
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
Use this to step through a reusable interview workflow for this problem.
Generate every possible combination without any filtering. At each of n positions we choose from up to n options, giving nⁿ total candidates. Each candidate takes O(n) to validate. No pruning means we waste time on clearly invalid partial solutions.
Backtracking explores a decision tree, but prunes branches that violate constraints early. Worst case is still factorial or exponential, but pruning dramatically reduces the constant factor in practice. Space is the recursion depth (usually O(n) for n-level decisions).
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.