Untitled

 avatar
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