Untitled
unknown
plain_text
2 months ago
2.0 kB
4
Indexable
import java.util.*; public class MaxLengthUnique { public int maxLength(List<String> arr) { return backtrack(arr, 0, new StringBuilder()); } private int backtrack(List<String> arr, int index, StringBuilder current) { if (index == arr.size()) { return current.length(); } // Take the current string int take = 0; String currentString = arr.get(index); if (isUnique(current, currentString)) { current.append(currentString); take = backtrack(arr, index + 1, current); current.setLength(current.length() - currentString.length()); // Backtrack } // Skip the current string int skip = backtrack(arr, index + 1, current); return Math.max(take, skip); } private boolean isUnique(StringBuilder sb, String currentString) { int[] charCount = new int[26]; for (int i = 0; i < sb.length(); i++) { charCount[sb.charAt(i) - 'a']++; if (charCount[sb.charAt(i) - 'a'] > 1) { return false; } } for (int i = 0; i < currentString.length(); i++) { charCount[currentString.charAt(i) - 'a']++; if (charCount[currentString.charAt(i) - 'a'] > 1) { return false; } } return true; } public static void main(String[] args) { MaxLengthUnique solution = new MaxLengthUnique(); List<String> arr1 = Arrays.asList("un", "iq", "ue"); System.out.println(solution.maxLength(arr1)); // Output: 4 List<String> arr2 = Arrays.asList("cha", "r", "act", "ers"); System.out.println(solution.maxLength(arr2)); // Output: 6 List<String> arr3 = Arrays.asList("abcdefghijklmnopqrstuvwxyz"); System.out.println(solution.maxLength(arr3)); // Output: 26 } }
Editor is loading...
Leave a Comment