Auto comment: topic has been updated by mzaferbooshi96 (previous revision, new revision, compare).

Another interesting problem from you, although much harder than the previous one. I will assume that the input is a string.

We can solve this with Divide and Conquer in a similar way that we would construct a segment tree. Let's create an array $$$a$$$, where $$$a_i$$$ is $$$1$$$ if $$$s_i$$$ is 'A', otherwise $$$a_i$$$ is $$$-1$$$. We can recursively calculate the difference between sum of the array by calculating the sum of the left part and the right part. Merging the result is trivial: $$$sum_{L, R} = sum_{L, M} + sum_{M + 1, R}$$$, where $$$M = \lfloor \frac{L + R}{2} \rfloor$$$.

If the sum of the array is positive, the answer is Anton, if it is negative, the answer is Danik, and if it is $$$0$$$ the answer is Friendship.

Time complexity: $$$O(n)$$$

Proof of time complexity: At avery level of the recursion where $$$L \neq R$$$, we split into two more recursions. We can model the recurrence as $$$T(n) = 2 \cdot T(\frac{n}{2}) + O(1)$$$. By the [Master Theorem](https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)) the time complexity is $$$O(n)$$$.

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6;
string s;
int n, a[N], cnt = 0;

int DnC(int L, int R) {
    cnt++;
    if (L == R) {
        return a[L];
    }
    int M = (L + R)/2;
    return DnC(L, M) + DnC(M + 1, R);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> s;
    n = s.length();
    for(int i = 0;i<n;++i) {
        a[i] = (s[i] == 'A' ? 1:-1);
    }
    int res = DnC(0, n - 1);
    if (res == 0) {
        cout << "Friendship" << endl;
    }
    else {
        cout << (res > 0 ? "Anton":"Danik") << endl;
    }
    return 0;
}