Problem statement Two players alternate turns on a binary string (consisting of '0's and '1's). On each turn, the current player removes any pair of adjacent different characters. The game ends when no such pair remains. The player who made more total moves wins. Print DA if the move counts differ, NET if they are equal.

Key observation The sequence of collapses is deterministic — no matter which valid pair each player picks, the same pairs disappear in the same relative order. The only thing that matters is how many collapses happen in total and whether that number is odd or even.

Because players alternate, player 0 scores the 1st, 3rd, 5th, … collapses and player 1 scores the 2nd, 4th, 6th, … If the total is odd, player 0 has one extra move — output DA. If even, both have the same count — output NET.

A stack lets us count those collapses in a single left-to-right pass: whenever the incoming character differs from the top of the stack, a collapse happens; otherwise push and continue.

Algorithm Initialise counters op0 = 0, op1 = 0, move index k = 0, and an empty stack. For each character s[i]: If the stack is non-empty and s[i] ≠ stack.top() → collapse. Award the point to player 0 if k is even, else player 1. Pop, increment k. Otherwise → push s[i]. After the scan, print DA if op0 ≠ op1, else NET.

Worked example — s = "010110" i s[i] stack top action k op0 op1 0 '0' — push '0' 0 0 0 1 '1' '0' '1'≠'0' → op0++, pop, k=1 1 1 0 2 '0' — push '0' 1 1 0 3 '1' '0' '1'≠'0' → op1++, pop, k=2 2 1 1 4 '1' — push '1' 2 1 1 5 '0' '1' '0'≠'1' → op0++, pop, k=3 3 2 1 op0 = 2, op1 = 1 → op0 ≠ op1 → verdict: DA

Solution (Java)

code 

import java.io.*; import java.util.*;

public class Game { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); PrintWriter pw = new PrintWriter(System.out); int t = Integer.parseInt(br.readLine());

while (t-- > 0) {
        String s = br.readLine();
        int n = s.length();
        int op0 = 0, op1 = 0, k = 0;
        Stack<Character> st = new Stack<>();

        for (int i = 0; i < n; i++) {
            if (!st.isEmpty() && s.charAt(i) != st.peek()) {
                if (k % 2 == 0) op0++;
                 else            op1++;
                k++;
                st.pop();
            } else {
                st.push(s.charAt(i));
            }
        }
        pw.println(op0 != op1 ? "DA" : "NET");
    }
    pw.flush();
}

}

Complexity time O(N) per test case space O(N) for the stack

Each character is pushed and popped at most once. Fast I/O (BufferedReader + PrintWriter) keeps the constant small.

Edge cases All identical characters — no collapses, both scores are 0 → NET. Single character — stack is always empty on first char, nothing ever collapses → NET. Alternating string — every character triggers a collapse; total collapses = n−1; result depends on parity.