Problem

A “tuple” is defined as an ordered collection of elements which can include duplicate values and each element is assigned an order. A tuple with n elements (a1, a2, a3, ..., an) can be expressed using the set notation in various ways, with any ordering of the subsets as:

{{a1}, {a1, a2}, {a1, a2, a3}, ..., {a1, a2, a3, ..., an}}

For example, the tuple (2, 1, 3, 4) can be represented as:

{{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

The sets can be permuted, but they still represent the same tuple:

{{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}
{{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}

Given a string s that represents a tuple in the form of a set of sets, you need to determine the elements of the tuple in their correct order. The string s is formatted with numbers and the characters {, }, and ,.

Constraints

• The length of s is between 5 and 1,000,000.
• s consists of numbers, {, }, and ,. No number starts with 0.
• s always correctly represents a tuple with no duplicate elements.
• The elements of the tuple are natural numbers between 1 and 100,000.
• The output array will have between 1 and 500 elements.

Example Inputs and Outputs

Explanation of Examples

• Example 1: The order in the sets varies but consistently starts from a smaller set to the full set representing the tuple. The tuple (2, 1, 3, 4) is formed by determining which elements appear as the sets grow.
• Example 2: Although the sets are given in a different order, they still indicate the same tuple as example 1.
• Example 3: (111, 20) is represented, and while the order in the set might suggest (20, 111), the tuple format ensures that 111 appears first since it’s isolated in a set by itself initially.
• Example 4: A single-element tuple is directly indicated.
• Example 5: By analyzing the growth of sets from smaller to larger, it can be discerned that the tuple is (3, 2, 4, 1).

The challenge involves parsing the string to extract sets, then determining the tuple order by the size of these sets and the introduction of new elements in each subsequent set.

How to Approach?

find one element tuple -> transform to integer and remove from total

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import java.util.*;

class Solution {
    public int[] solution(String s) {
        // Remove the outermost braces and split the string by "},{"
        String[] tuples = s.substring(2, s.length() - 2).split("\\},\\{");
        Arrays.sort(tuples, (a, b) -> a.length() - b.length()); // Sort by length
        
        Set<Integer> seen = new HashSet<>();
        List<Integer> result = new ArrayList<>();
        
        // Process each group of numbers
        for (String tuple : tuples) {
            String[] nums = tuple.split(",");
            for (String num : nums) {
                int value = Integer.parseInt(num.trim());
                if (seen.add(value)) { // Add only if not already added
                    result.add(value);
                }
            }
        }
        
        // Convert List<Integer> to int[]
        return result.stream().mapToInt(i -> i).toArray();
    }
}