Bob has a string s consisting of lowercase English letters. He defines s' to be the…
- User
Bob has a string s consisting of lowercase English letters. He defines s' to be the string after removing all "a" characters from s (keeping all other characters in the same order). He then generates a new string t by concatenating s and s'. In other words, t=s+s' (look at notes for an example).
You are given a string t. Your task is to find some s that Bob could have used to generate t. It can be shown that if an answer exists, it will be unique. Input
The first line of input contains a string t (1 ≤ |t| ≤ 10^5) consisting of lowercase English letters.
Output
Print a string s that could have generated t. It can be shown if an answer exists, it is unique. If no string exists, print ":(" (without double quotes, there is no space between the characters).
Examples
Input
aaaaa
Output
aaaaa
Input
aacaababc
Output
:(
Input
ababacacbbcc
Output
ababacac
Input
baba
Output
:(
Note
In the first example, we have s = "aaaaa", and s' = "".
In the second example, no such s can work that will generate the given t.
In the third example, we have s = "ababacac", and s' = "bbcc", and t = s + s' = "ababacacbbcc".
Assistant
We need to solve: Given t, find s such that t = s + s', where s' is s with all 'a' characters removed. All characters are lowercase letters.
We are told that if solution exists, it's unique. If not, output ":(".
Constraints: |t| up to 1e5.
We need to derive s. Let's denote n = |t|.
We have s (unknown length), and s' (the string of non-'a' characters of s) concatenated after s. So t = s concatenated with s'. So t's first |s| characters are s. Then the remaining part of t must equal s'.
Thus we can think: Let m = length of s (unknown). Then the length of t = n = m + len(s').
But s' is derived from s: it contains exactly the characters from s that are not 'a'. So number of non-'a' characters in s = length of s'. Let that count = k. Then n = m + k. So m = n - k.
Now k is the number of non-'a' characters in s. But s is the prefix of t of length m. So we can compute the number of non-'a' characters in that prefix; call it c. Then we need c = k, and also the suffix (positions m to n-1) must equal exactly the sequence of non-'a' characters in s.
We need to find m such that:
- Let s = t[0:m].
- Let non-a count in s = count of characters != 'a' in s.
- Then the remaining part of t (t[m:]) should be exactly the string consisting of all characters of s that are not 'a', in order.
Additionally, m must be integer and obviously m <= n.
Also note that if s contains many 'a's, then s' is shorter than s.
Goal: find m satisfying conditions.
We can attempt to iterate over possible m? n up to 1e5, so O(n) or O(n log n) okay, but we cannot try all m naively with O(n) each? However we can precompute counts of non-a prefix, and also maybe precompute the sequence of non-a characters from the beginning.
Idea: For each candidate m, we need to check if the suffix matches the non-a subsequence of prefix. But m can be up to n. However we can use two-pointer technique to verify in O(n) total if we try all? But we only need the unique solution.
We can derive m from the condition n = m + count_non_a(s). Since count_non_a(s) is unknown until we know s (which is determined by m). So we need to solve for m.
Let’s denote P[i] = number of non-'a' characters in t[0:i] (prefix up to i, i from 0 to n). So P[0]=0. For each index i (1-indexed maybe), P[i] = number of non-a in first i chars.
If we assume s = t[0:m], then count_non_a(s) = P[m]. Then total length n = m + P[m]. So m must satisfy: m + P[m] = n.
Thus we have a simple equation: m + P[m] = n.
That's a necessary condition (derived from length). Also m must be between 0 and n inclusive, but s can be empty? Input t length >=1, but s must be such that t = s+s'. Could s be empty? If s empty, s' empty, then t empty. But t length >=1, so s cannot be empty. So m >= 1.
Now we can compute P[i] for all i (0..n). Then find m such that m + P[m] = n.
But there could be multiple m that satisfy? The problem says solution is unique if exists, but could multiple m satisfy that equation? Possibly yes, but maybe only one also satisfies the matching condition. However we can use this to narrow down candidates.
Observation: Since P[m] is non-decreasing, m + P[m] is strictly increasing? Let's check: as m increases by 1, P[m] either stays same (if new char is 'a') or increases by 1 (if non-a). So m + P[m] increases by either 1+0 =1 or 1+1=2. So m+P[m] is strictly increasing (since at least +1). So it is monotonic strictly increasing. Therefore there can be at most one m satisfying m+P[m] = n. Because as m increases, the sum increases continuously, so if it hits n at some m, it cannot hit again. Good.
Thus we can compute m uniquely as the index such that m + P[m] = n, if exists. But careful: m is the length of s, which is prefix of t. Since P is computed on t, but note that s is the prefix of length m. However t contains the whole string s and then s'. The P we compute on t prefix up to m is exactly count_non_a(s). That's fine because t's first m characters are s. So m+P[m]=n is necessary.
But is it sufficient? Not necessarily: we also need that the suffix (t[m:]) exactly matches the non-a characters in s. So we need to verify that condition. If it holds, then s is valid; else no solution.
Thus algorithm:
- Input t, n = len(t)
- Compute array P: prefix counts of characters not equal to 'a'. For i from 0 to n (i is length of prefix). Usually: P[0] = 0; for i in 1..n: P[i] = P[i-1] + (t[i-1] != 'a').
- For each possible m from 0 to n (but m must be >=1 for non-empty s? However t may be like "a" where s="a", s'="" so m=1, P[1]=0, n=1 => 1+0=1. So m=0 is only if n=0, not possible. So we can ignore m=0.)
- But we can find m such that m + P[m] == n.
Since m+P[m] is strictly increasing, we can binary search or just linear scan. However we can compute directly: iterate m from 1 to n, check if m+P[m] == n. But O(n) is fine (1e5). Actually we might even binary search because it's monotonic. But O(n) is fine.
But careful: There is also possibility that m is not found, i.e., no m satisfies equation. Then output ":(".
If found, let m = candidate. Then we need to verify that t[m:] equals the sequence of non-'a' characters from t[0:m]. We can extract s = t[:m] and compute expected s' by removing 'a's from s. Then compare to t[m:]. If equal, output s; else output ":(".
This seems straightforward.
But need to think about edge cases: what if m is such that t[m:] length != P[m]? But we already have m+P[m]=n => n-m = P[m], so length of suffix equals P[m]. So lengths match. But content must match.
Now, is there any situation where m+P[m]=n but verification fails? Possibly yes, e.g., t = "aacaababc" from second example. Let's compute.
We'll test example 2: t = "aacaababc". Let's compute n=9. Compute P: indices 0..9.
t: a a c a a b a b c? Actually "aacaababc": let's write: positions 1..9: 1:a,2:a,3:c,4:a,5:a,6:b,7:a,8:b,9:c.
Count non-a: at i=0 P0=0; i=1: a -> 0; i=2: a ->0; i=3: c ->1; i=4: a ->1; i=5: a ->1; i=6: b ->2; i=7: a ->2; i=8: b ->3; i=9: c ->4. So P: [0,0,0,1,1,1,2,2,3,4]
Compute m+P[m] values: m=1:1+0=1 2:2+0=2 3:3+1=4 4:4+1=5 5:5+1=6 6:6+2=8 7:7+2=9 8:8+3=11 9:9+4=13
Only m=7 gives 9. So m=7. s = t[0:7] = "aacaaba"? Actually first 7: indices 0..6: a,a,c,a,a,b,a -> "aacaaba"? Wait t[0:7] = "aacaaba"? Let's confirm: positions 1-7: a a c a a b a => "aacaaba". That's s. Then expected s' = remove 'a's: from s: a,a,c,a,a,b,a -> non-a: c and b => "cb". t[7:] = positions 8-9: b,c? Actually indices 7 and 8 (0-based). t[7] = b, t[8]=c => "bc". But expected "cb" not equal, so fails. So output ":(". This matches example.
Now example 3: t = "ababacacbbcc". n=12? Actually "ababacacbbcc" length: a b a b a c a c b b c c? Let's count: a b a b a c a c b b c c => 12. Compute prefix non-a counts: letters not 'a': b, b, c, c, b, b, c, c? Wait need to compute carefully.
t: indices 0:a,1:b,2:a,3:b,4:a,5:c,6:a,7:c,8:b,9:b,10:c,11:c? Actually "ababacacbbcc": break: a b a b a c a c b b c c. So non-a: positions 1(b),3(b),5(c),7(c),8(b),9(b),10(c),11(c) => 8 non-a. So P: i=0:0 i=1: t[0]=a ->0 i=2: t[1]=b ->1? Actually P[i] = count non-a in first i characters. So: i=1: first char a => 0 i=2: first two chars a,b =>1 i=3: a,b,a =>1 i=4: a,b,a,b =>2 i=5: a,b,a,b,a =>2 i=6: +c =>3? Let's systematic:
i:0->0 i=1 (char0 a):0 i=2 (char1 b):1 i=3 (char2 a):1 i=4 (char3 b):2 i=5 (char4 a):2 i=6 (char5 c):3 i=7 (char6 a):3 i=8 (char7 c):4 i=9 (char8 b):5 i=10 (char9 b):6 i=11 (char10 c):7 i=12 (char11 c):8
So P: [0,0,1,1,2,2,3,3,4,5,6,7,8]
Now m+P[m] must equal n=12. Compute: m=1:1+0=1 2:2+1=3 3:3+1=4 4:4+2=6 5:5+2=7 6:6+3=9 7:7+3=10 8:8+4=12 -> m=8 yields 12. m=9:9+5=14 >12, so m=8 is candidate.
s = t[0:8] = "ababacac"? Actually first 8: indices 0-7: a,b,a,b,a,c,a,c => "ababacac". That's the example. s' = remove 'a's: b,b,c,c => "bbcc"? Wait remove 'a' from "ababacac" yields: b,b,c,c? Actually s: a b a b a c a c -> non-a: b, b, c, c => "bbcc". t[8:] = indices 8-11: b,b,c,c => "bbcc". matches. So output s = "ababacac". Good.
Now example 1: t="aaaaa", n=5. Prefix non-a counts all 0. P: [0,0,0,0,0,0]. m+P[m] values: m=1:1+0=1, 2:2, 3:3, 4:4, 5:5. So m=5 gives 5. s = "aaaaa". s' = "", t[5:] = "" matches. Output "aaaaa". Good.
Example 4: t="baba". n=4. t: b a b a. P: i0=0,i1:b->1,i2:ba->1,i3:bab->2,i4:baba->2. m+P[m]: 1:1+1=2, 2:2+1=3,3:3+2=5,4:4+2=6. None equals 4. So no m; output ":(". That matches.
Thus the algorithm works for examples.
Edge Cases: What about t empty? Not possible as per constraints (1 ≤ |t|). But anyway.
What about s containing all non-a characters? Then s' = s, so t = s + s, so t would be twice s. But then m = n/2? Let's test: s = "bc", s' = "bc", t="bcbc", n=4. Compute P: b (non-a) =>1, c=>2? Actually prefix counts: i0=0,i1=1,i2=2,i3=2? Wait t="bcbc": indices:0:b,1:c,2:b,3:c. P[0]=0,P[1]=1,P[2]=2,P[3]=2? Actually careful: first 2 chars: b,c => both non-a, so P[2]=2; first 3 chars: b,c,b => all non-a => P[3]=3? Wait: Each char is non-a, so P[i]=i for i<=4? But t length is 4, so compute: P[0]=0; after char0 (b): P[1]=1; after char1 (c): P[2]=2; after char2 (b): P[3]=3; after char3 (c): P[4]=4. So m+P[m] values: m=1:1+1=2; m=2:2+2=4 => m=2 gives 4 (n). So s = t[:2]="bc". s' = "bc", t[2:]="bc", matches. Works.
What about s having mixture but the condition m+P[m]=n holds but the suffix does not match? That would cause output ":(". That is possible as in example 2. So need verification.
Complexity: O(n) time, O(n) space for t string and maybe extra array for P, but we can compute P on the fly while scanning for candidate? We need to know P[m] for each m, but we can compute prefix counts in an array of length n+1. That's O(n). Then find m via loop: for m in range(n+1) but m up to n, but only one candidate. Actually we can compute m by scanning from 0 to n and break when m+P[m]==n. Since it's strictly increasing, we can also binary search: but scanning O(n) fine.
But careful: The array P is length n+1, and we need to check each m. Since n=1e5, O(n) is fine.
After obtaining m, we need to verify: we can iterate over s (prefix) and collect non-a characters into a list/string, then compare to t[m:]. That is O(n). Or we can simultaneously traverse s and suffix using two pointers to check without building extra string: but building is fine.
But note: The condition m+P[m] = n gave us m. However, is it possible that m > n? No, m is length of prefix, so m <= n.
Also, what if m = n? Then P[m] must be 0. That means s has no non-a characters, i.e., all 'a's. Then s' = "" and t = s + "" = s, so t is all 'a's. That works as example.
Now what if m = 0? Not possible as t length >0.
Thus algorithm seems correct.
But is there any subtlety? Let's consider scenario where there might be multiple possible m if m+P[m] is not strictly increasing? Let's verify monotonicity: For each increase of m by 1, P[m] either stays same or increases by 1. So delta = 1 + (increase in P) which is either 1 or 2. So it's always >=1, strictly increasing. So yes, unique m if exists.
But note: This monotonicity holds for P defined on the prefix of t. However, we must ensure that we are using the same t that includes both s and s'. But P[m] counts non-a in prefix of t which is s. That's correct. So the sum is strictly increasing. So unique.
Thus the algorithm is simple.
Now let's confirm with some more edge cases.
Case: t = "a". n=1, P[1]=0, m=1 works, s="a", s'="", t[1:]="" matches. Output "a".
Case: t = "b". n=1, P[1]=1, m+P[m] = 1+1=2 >1, so no m. So output ":(". But is there an s? s would have to be something that after concatenating s' yields "b". Suppose s = "b", then s' = "b" (since no a removal? Actually s' removes all 'a's, s="b" has no 'a', so s' = "b". Then t = s+s' = "bb", not "b". So impossible. s = "a"? s' = "", t="a". No. So indeed no solution. Good.
Case: t = "ab". n=2. Compute P: i0=0,i1: a->0,i2:ab->1. m+P[m]: m=1:1+0=1; m=2:2+1=3. None equals 2 -> no solution? Check manually: s candidates? If s="a", s'="", t="a". Not match. s="ab", s'="b", t="abb". Not match. s="b"? length 1? Actually s length must be m such that t = s+s'. For t="ab", possible s? Suppose s="ab"? t would be "ab"+"b" = "abb". So no. So indeed no solution. Good.
Case: t = "aba". n=3. P: i0=0,i1: a->0,i2:ab->1,i3:aba->1? Actually non-a: b only -> 1. So P[1]=0,P[2]=1,P[3]=1. m+P: m=1:1+0=1; m=2:2+1=3 => m=2 works? n=3, yes. s = t[:2] = "ab". s' from s: remove 'a' -> "b". t[2:] = t from index 2 = "a"? Wait t="aba": indices 0:a,1:b,2:a. t[2:] = "a". But expected s' = "b". Not match. So verification fails => output ":(". Let's test manually: Could there be s? s = "aba"? then s' = "b", t = "abab". Not match. s = "a"? then s'="", t="a". Not match. So no solution. Good.
Case: t = "abba". n=4. t: a b b a. P: i0=0,i1:0,i2:1,i3:2,i4:2. m+P: m=1:1+0=1, m=2:2+1=3, m=3:3+2=5, m=4:4+2=6. No 4. So no solution. But consider s="ab", s'="b", t="abb". Not match. So fine.
Case: t = "bb". n=2. P: i0=0,i1:1,i2:2. m+P: m=1:1+1=2 => m=1 candidate. s = t[:1] = "b". s' expected: from s remove 'a's => "b". t[1:] = "b". matches. So s="b". That is interesting: t = "bb", s="b", s' = "b". Works. So our algorithm would give m=1 because 1+P[1] = 1+1=2. So output "b". That is correct. Indeed Bob could have used s = "b". So t = "b" + "b" = "bb". So it's valid.
Check: s length 1, s' length 1, total 2.
Case: t = "bcbc": we already did yields s="bc".
Case: t = "abcabc"? Let's test: t = "abcabc", n=6. P: a:0? Actually count non-a: a is a, so non-a: b,c? So t: a,b,c,a,b,c. Prefix counts: i0=0,i1:0,i2:1,i3:2,i4:2,i5:3,i6:4? Wait after index3 (a,b,c,a) -> non-a: b,c =>2; after index4 (a,b,c,a,b) -> non-a: b,c,b =>3; after index5 (all) -> non-a: b,c,b,c =>4. So P: [0,0,1,2,2,3,4] (i0..6). Compute m+P: m=1:1+0=1;2:2+1=3;3:3+2=5;4:4+2=6 => m=4 gives 6. s = t[:4] = "abca". s' = remove 'a's -> "bc". t[4:] = "bc". Works? t[4:] = indices 4,5: b,c => "bc". Yes matches. So s="abca". But wait is that consistent? s = "abca", s' = "bc", t = "abca"+"bc" = "abcabc". Yes correct. So algorithm works.
But is there any case where m+P[m]=n holds but suffix matches partially but not fully? That would fail verification.
Now we need to be careful about the verification: t[m:] should equal exactly the subsequence of non-'a' characters from s (which is the prefix). It's easy to compute.
Now think about the uniqueness and existence: The problem states that if answer exists it's unique. Our method finds at most one m by the equation, then verifies.
But is the equation m+P[m]=n also necessary? Yes because total length is m + (number of non-a in s). Since s is prefix, that number is exactly P[m]. So it's necessary.
Thus solution: compute prefix count of non-a. For each m from 0..n (though we can start 1), if m+P[m]==n, then candidate. Then verify.
We could also compute m directly by solving: Let x = number of non-a in prefix? But better just iterate.
Time O(n). Memory O(n) for P array or we could compute on the fly? Since we need P[m] for each m, we could compute an array of length n+1 storing counts. Or we can compute a list of non-a counts while scanning and store, which is trivial.
Implementation details:
Read t as string, n = len(t). Initialize prefix = [0]*(n+1) for i in range(1,n+1): prefix[i] = prefix[i-1] + (t[i-1] != 'a') Then m = None for i in range(1, n+1): if i + prefix[i] == n: m = i break If m is None: print(":(") Else: s = t[:m] expected_s_prime = ''.join([c for c in s if c != 'a']) if t[m:] == expected_s_prime: print(s) else: print(":(")
But careful: t[m:] length = n-m, expected_s_prime length = prefix[m]. Since we have m+prefix[m]=n, they are equal length. But we must ensure that the expected_s_prime exactly matches t[m:]. If yes, output s.
Now consider edge case where m = n? Then t[m:] is empty, expected_s_prime must be empty, which implies prefix[n] = 0, so all characters 'a'. That works.
Now what about when m=0? We ignore.
Now verify that we haven't missed any scenario where s may exist even if m+P[m]!=n? Could there be a scenario where the non-a characters of s are exactly the suffix but the prefix s might include some characters from the suffix? Wait the definition: t = s + s'. That means the first part is s, then the second part is s' (the removal of all 'a's from s). So the length condition is necessary. So no.
Now we should also consider the case where s' could contain 'a'? No, because s' is defined by removing all 'a's, so it contains no 'a's. Thus the suffix of t (t[m:]) should contain no 'a' characters. That is an additional necessary condition we might check early, but verification covers it.
But note: Even if the suffix contains 'a's, the equation could hold but verification fails. But perhaps we can use this as a quick check: if t[m:] contains any 'a', then no solution. But not needed.
Now, is there any scenario where the equation yields an m that is not integer? No, m is integer.
Now, confirm that the algorithm always finds unique m if solution exists: Suppose there is a solution with s of length m. Then P[m] = count_non_a(s) = len(s'), and n = m+len(s') => m+P[m]=n. So the equation holds. And since the sum is monotonic, that m is the unique index satisfying the equation. So algorithm will find it. Then verification will succeed because s' matches t[m:]. So it outputs s. Good.
Now, is there any scenario where there are multiple m satisfying equation but monotonicity prevents? But we proved monotonic strictly increasing, so at most one.
Thus solution is correct.
Now, we need to be cautious about memory and speed: 1e5 is fine.
Now we can provide the final answer.
But I should also consider if t contains newline etc. Input is single line.
Now implement in Python 3.
We can further optimize by not storing P as list; we can compute m by scanning while computing prefix counts. But we need to know prefix count for each i to check equation. We could compute on the fly and store candidate when condition met. However we also need P[m] later for verification? Actually we only need s and then compute expected_s_prime, no need for P[m] after that. But we need to know m. So we can compute while scanning, and when condition holds, record m. However, we need to ensure that the condition is based on prefix count up to that point. But if we scan from left to right, we can compute current prefix count. But we also need to know t[m:] for verification. So we can record the index m.
But we must also ensure that the condition is unique: The monotonic property ensures that once we find such m, it's the only one. However, we cannot guarantee that there isn't another m later? Since it's strictly increasing, if we find an m that satisfies, the sum for larger m would be > n, so no more. So it's safe to break.
Thus we can implement as:
def solve(): t = input().strip() n = len(t) prefix_non_a = 0 m = -1 for i, ch in enumerate(t, start=1): # i from 1 to n inclusive if ch != 'a': prefix_non_a += 1 if i + prefix_non_a == n: m = i break # But careful: We need prefix_non_a counts of first i characters. In loop, when we see ch at index i-1, after processing, prefix_non_a is count of non-a in first i characters. So condition i + prefix_non_a == n is correct.
# However, we need to ensure that we also consider the case where m = n (i = n) and the condition holds? Yes, loop includes i=n. if m == -1: print(":(") return s = t[:m] expected = ''.join([c for c in s if c != 'a']) if t[m:] == expected: print(s) else: print(":(")But careful: In the loop, we are incrementing prefix_non_a before checking condition for the same i. That's correct: after processing character i, prefix count is for length i. So condition is correct.
But what about the scenario where the condition could be satisfied at i=0? Not needed because i starts from 1, and i=0 is not valid as s non-empty; but if t is empty? Not applicable.
Now test with examples:
Example 1: t="aaaaa". Loop: i=1, ch='a', prefix_non_a stays 0, i+prefix=1 => not 5. i=2: sum=2 i=3:3 i=4:4 i=5:5 -> condition true, m=5. Works.
Example 2: t="aacaababc". Let's simulate quickly: n=9. Initialize p=0. i=1:'a' p=0, sum=1 i=2:'a' p=0 sum=2 i=3:'c' p=1 sum=4? i=3+1=4 not 9 i=4:'a' p=1 sum=5 i=5:'a' p=1 sum=6 i=6:'b' p=2 sum=8 i=7:'a' p=2 sum=9 => condition true, m=7. So we break. Then s = t[:7] = "aacaaba"? Actually t[0:7] = "aacaaba"? Wait our earlier s was "aacaaba"? Actually t[:7] = first 7 characters: indices 0-6: a,a,c,a,a,b,a -> "aacaaba". Yes. Then expected = remove a's: "cb". t[7:] = from index 7: "bc". Not equal => print ":(".
Matches.
Example 3: t="ababacacbbcc". n=12. Loop: i=1:'a' p=0 sum=1 i=2:'b' p=1 sum=3? 2+1=3 i=3:'a' p=1 sum=4 i=4:'b' p=2 sum=6 i=5:'a' p=2 sum=7 i=6:'c' p=3 sum=9 i=7:'a' p=3 sum=10 i=8:'c' p=4 sum=12 => condition true m=8. s = "ababacac". expected remove a: "bbcc"? Wait we need to compute: s = "ababacac": chars: a,b,a,b,a,c,a,c -> non-a: b,b,c,c -> "bbcc". t[8:] = from index 8: "bbcc". So matches. Print s.
Example 4: t="baba". n=4. Loop: i=1:'b' p=1 sum=2 i=2:'a' p=1 sum=3 i=3:'b' p=2 sum=5 >4, break? Actually we continue until i=4? But we break only when condition true. Condition not true at i=1,2,3,4? i=4: ch='a', p stays 2, sum=6. No true. So m remains -1 => print ":(".
Works.
Now test other cases:
t="bb": n=2. Loop: i=1:'b', p=1, sum=2 => condition true, m=1. s="b", expected="b", t[1:]="b", match. Print "b". Good.
Now t="abcabc": n=6. Loop: i1:'a' p=0 sum=1 i2:'b' p=1 sum=3 i3:'c' p=2 sum=5 i4:'a' p=2 sum=6 => m=4. s="abca"? Actually t[:4] = "abca", expected remove a: "bc", t[4:]="bc". Yes. Output "abca". That seems correct.
Now check t="a". n=1. Loop i=1:'a' p=0 sum=1 => m=1, s="a", expected="", t[1:]="" => print "a". Good.
Now t="aaab": n=4. Loop: i1:'a' p=0 sum=1 i2:'a' p=0 sum=2 i3:'a' p=0 sum=3 i4:'b' p=1 sum=5 -> not 4. So no m => ":(". Check manually: s must satisfy? If s="a", s'="", t="a". No. s="aa", s'="", t="aa". No. s="aaa", s'="", t="aaa". No. s="aaab", s'="b", t="aaabb". No. So no solution. Good.
Now t="aba": we saw no solution. Loop: n=3, i1:'a' p=0 sum=1; i2:'b' p=1 sum=3 => m=2? Actually 2+1=3 => condition true, m=2. Then s="ab", expected="b", t[2:]="a", fails -> output ":(".
Thus algorithm works.
Now, we might also think about corner case where t contains only 'a's and some other characters but maybe m found is not valid due to mismatch, but we already check.
Now, one more nuance: The prefix non-a count we compute is based on t, but t includes both s and s'. However, when we consider i up to n, we are counting non-a characters in the prefix of t which includes s fully and possibly part of s'? Wait careful: In our loop, i runs from 1 to n, and we are computing the prefix count of t[0:i] (the first i characters). For i <= m, that's exactly counting within s. For i > m, we are counting characters that include s and part of s'. But our condition is only checked for i that satisfy i + prefix[i] == n. For i <= m, prefix[i] = count in s prefix. But could there be an i > m that also satisfies the equation? Possibly? Since the sum i+prefix[i] is strictly increasing, if at i=m we have sum = n, for i>m, sum > n, so no. But what if m is less than something and i>m could also produce sum = n? Since strictly increasing, no. So we only need to check i from 1 to n, but for i > m, prefix[i] includes characters from s', so the condition i+prefix[i]==n might never be satisfied because i+prefix[i] > i + prefix[m] + (something) maybe? Let's check if it could exactly equal n? Since at i=m, sum = n. For i=m+1, sum increases by at least 1, so becomes at least n+1. So cannot equal n. So the only candidate is i <= m. So it's fine to compute over all i.
Thus implementation is good.
But there is a subtlety: In the loop, we are incrementing prefix_non_a based on t[i-1]. For i up to n, we are counting non-a in the whole t. For i > m, that includes s' characters. But we break when we find candidate, so we never process i>m if candidate found early. That's fine. And if candidate not found, we process all i. That's fine.
Now, is it possible that candidate m found but actually m is not the length of s because the condition might be satisfied by an i that includes some characters from s'? Wait, as argued, due to monotonicity, the only index that satisfies i+prefix[i]=n must be exactly the length of s if solution exists. But if no solution exists, could there be an index i (maybe > the hypothetical s length) that satisfies the equation, leading to a false candidate? For example, t = "aacaababc" we got i=7 satisfying, but that i gave a candidate but verification failed. That is allowed. But could there be a case where i satisfying equation yields a false positive (i.e., verification passes) but that s is not actually the original? The problem says that if answer exists, it's unique. But could there be multiple s that generate the same t? They say it's unique if exists. So it might be possible that a false candidate passes verification, producing an s that would generate t, which would be a valid answer. But then that s is the answer. However, could there be a scenario where the equation gives i that is not the length of s (no solution) but verification passes? That would imply that t = s + s' with s = t[:i] and s' = t[i:] = remove a from s. So that is actually a valid solution. So if verification passes, it is a valid solution regardless of whether we derived i from the equation? But the equation is derived from length, so if verification passes, then length condition must hold. So it's consistent.
Thus our algorithm correctly identifies valid solutions.
Now time complexity O(n). Space O(1) aside from input and maybe building expected string.
But note: building expected string of length up to n could be O(n) memory; but it's okay.
Alternatively, we can verify without constructing expected string by iterating through s and comparing to t[m:] using two pointers: i over s, j over t[m:]; if s[i]!='a', we check s[i]==t[m+j] and increment j; if s[i]=='a', skip; after processing all s, j should equal len(t[m:]) and all characters matched. That also works in O(n) with O(1) extra memory. But building a string is fine.
But note that t can be up to 1e5, and constructing expected string of length up to ~n/2? worst-case if s has no 'a's, then length of s' = m, and m+P[m] = n => m+m = n => m = n/2, so expected length = m = n/2, about 5e4, fine.
However, constructing expected string may double memory, still within limit.
We'll implement simply.
But watch out: Python's string concatenation in loop might be inefficient, but using list comprehension or filter is okay.
Now consider input with large n 100k, building expected string using list comprehension is fine.
Implementation details:
def solve(): t = sys.stdin.readline().strip() n = len(t) p = 0 m = -1 for i,ch in enumerate(t, 1): # i from 1 to n if ch != 'a': p += 1 if i + p == n: m = i break if m == -1: print(":(") return s = t[:m] # compute s' s_prime = ''.join([c for c in s if c != 'a']) if t[m:] == s_prime: print(s) else: print(":(")
Now, there is a nuance: In the loop, we break as soon as we find m. But consider scenario where there is no solution, but later i satisfies i+p == n? Actually because the function is strictly increasing, if we go through all i, only one i can possibly satisfy if any. But if we break early on a false candidate, that's fine because if it's false, verification fails and we output ":(". However, what if there is a later i that would be true? Since function is strictly increasing, if at i1 we have i1+p1 = n, then for i2 > i1, i2+p2 > i1+p1 = n, so cannot equal. So there cannot be a later true candidate. So breaking at first is safe.
But what about i where i+p == n but we haven't processed all characters yet? That's fine because we have read up to index i-1. However, to compute s and s' we need the full t. We have t fully, so we can slice.
Now test with scenario where the candidate is m = n? Then p must be 0. In loop, we process all characters up to i=n, p should be 0 if all 'a's. So condition i+p == n gives n+0 = n -> true. So m = n. Then s = t, s' = ''; t[n:] = ''; matches.
Now test scenario where t = "aab". n=3. Loop: i=1:'a' p=0 sum=1 i=2:'a' p=0 sum=2 i=3:'b' p=1 sum=4 -> no candidate => ":(". Check manually: s possible? s="a" -> t="a"+" "="a". No. s="aa"-> t="aa"+" "="aa". No. s="aab"-> s'="b", t="aabb". No. So indeed no.
Now test scenario t = "abacaba"? Actually let's try t = "abacabac". Could be something.
Now also consider scenario where t has no 'a's except maybe. For t="bcbc", we got m=2.
Now we should consider input reading: The problem statement says "The first line of input contains a string t". So just one line.
Now final answer.
But before finalizing, we should consider if there is any case where the equation i + p_i = n yields an integer i, but i > the length of s? But we argued monotonic ensures uniqueness. But what if there is no solution but i + p_i = n holds for some i, but verification fails, we output ":(". That's correct.
Now let's verify with a more tricky case: Suppose t = "c". n=1. p=1 at i=1? Actually t="c", loop: i=1, ch='c', p=1, i+p=2 !=1 => no candidate, output ":(". But maybe s = ""? Not allowed. So correct.
Now consider t = "aa". n=2. i=1 p=0 sum=1; i=2 p=0 sum=2 => candidate m=2. s="aa", s'="", t[2:]="" => output "aa". That's valid: s="aa", s'="", t="aa". Indeed Bob could have used s="aa".
Now consider t = "aabaa"? Let's test: t = "aabaa". n=5. Compute p: i1:'a' p=0 sum=1; i2:'a' p=0 sum=2; i3:'b' p=1 sum=4; i4:'a' p=1 sum=5? 4+1=5 -> m=4? Actually i=4 gives sum=5? Let's calculate: i=4, p after processing char4 (a) remains 1, i=4, p=1 -> sum=5, which equals n=5. So m=4. s = t[:4] = "aaba". s' = remove a -> "b". t[4:] = "a"? Actually t[4] is index 4? t indices 0-4: a a b a a? Wait string "aabaa": indices:0:a,1:a,2:b,3:a,4:a. s = first 4 chars: indices 0-3: a,a,b,a => "aaba". s' = "b". t[4:] = index 4: "a". Not match. So output ":(". Check if any s exists? s="a", s'="" -> t="a". No. s="aa", s'="" -> "aa". s="aab", s'="b" -> t="aabb". No. s="aaba", we already tried. s="aabaa", s'="b"? Actually s' from s "aabaa" remove a -> "b"? Wait s="aabaa": non-a: b -> "b", t would be "aabaa"+"b" = "aabaab". No. So indeed no.
Thus algorithm works.
Now, we must also consider if the string may have newline characters, we use strip.
Now, we will provide final solution.
But we should also consider potential integer overflow? Not with Python.
Now we can produce final answer.
But the problem statement might have some tricky note: "It can be shown that if an answer exists, it will be unique." Good.
Now, a subtlety: When we compute p in loop, we are using the entire t. However, if there is a candidate m, the prefix we used to compute p includes only the first m characters (since we break early). That's correct.
But what if we break early but the candidate m is such that i+p == n, but we haven't processed characters after i? That's fine because we have t already.
Now, what about the case where the candidate m is found but we haven't yet processed the character at index m-1? Actually in the loop, when i=m, we have processed characters up to index m-1. That's exactly the first m characters. So we have computed p = non-a count in first m chars. So condition holds.
Now, need to ensure that if there are multiple possible candidates, but we break on first, but monotonic ensures only one, so fine.
Now, is there any scenario where m might be 0? Not needed.
Now, we could also compute m by solving equation using binary search, but not necessary.
Now we should also consider memory for building expected s'. We can also verify without building:
def verify(s, suffix): j=0 for ch in s: if ch != 'a': if j >= len(suffix) or suffix[j] != ch: return False j += 1 return j == len(suffix)
That's efficient and uses no extra memory for building string.
But both are fine.
Now, we must output exactly ":(" without spaces.
Now, consider case where t has trailing newline? strip handles.
Now, final solution in Python:
import sys
def main(): t = sys.stdin.readline().strip() n = len(t) p = 0 m = -1 for i,ch in enumerate(t, start=1): if ch != 'a': p += 1 if i + p == n: m = i break if m == -1: print(":(") return # verify s = t[:m] suffix = t[m:] j = 0 for ch in s: if ch != 'a': if j >= len(suffix) or suffix[j] != ch: print(":(") return j += 1 if j != len(suffix): print(":(") return print(s)
if name == "main": main()
Let's test with given examples.
Example 1: t="aaaaa" n=5 i=1:'a' p=0 sum=1; i=2: sum=2; i=3: sum=3; i=4: sum=4; i=5: sum=5 => m=5 s="aaaaa", suffix="", verification: all chars 'a' so skip; j=0; check j==0 -> print "aaaaa". Works.
Example 2: t="aacaababc" n=9 i=7 triggers m=7; s="aacaaba" (actually t[:7]="aacaaba"), suffix="bc" Verification: iterate s: a (skip), a (skip), c (non-a) -> check suffix[0]='b'? mismatch => print ":(". Good.
Example 3: t="ababacacbbcc" n=12 i=8 triggers m=8; s="ababacac", suffix="bbcc" Verification: a skip, b non-a -> suffix[0]='b' matches j=1; a skip; b non-a -> suffix[1]='b' matches j=2; a skip; c non-a -> suffix[2]='c' matches j=3; a skip; c non-a -> suffix[3]='c' matches j=4; end s, j=4 equals len(suffix)=4 => print s. Works.
Example 4: t="baba" n=4; loop finishes no m => print ":(". Good.
Thus correct.
Now consider potential pitfalls:
-
The problem constraints say |t| up to 100000, so Python string operations are fine.
-
Might need to use fast I/O? Not necessary.
Now finalize answer.
But we should also mention the reasoning in solution: find m such that m + count_non_a(t[:m]) = n; then check.
Now produce final answer accordingly. ```python import sys
def solve() -> None: t = sys.stdin.readline().strip() n = len(t)
# Find candidate length m such that m + (# of non-'a' in first m chars) = n non_a = 0 # count of characters != 'a' in prefix m = -1 for i, ch in enumerate(t, start=1): # i = length of prefix processed if ch != 'a': non_a += 1 if i + non_a == n: m = i break if m == -1: print(":(") return s = t[:m] suffix = t[m:] # Verify that suffix equals s with all 'a' removed j = 0 # index in suffix for ch in s: if ch != 'a': if j >= len(suffix) or suffix[j] != ch: print(":(") return j += 1 if j != len(suffix): print(":(") return print(s)if name == "main": solve()