# PROBLEM LINK

# DIFFICULTY

MEDIUM

# PREREQUISITES

Simple Math, Binomial Coefficient

# PROBLEM

You are given a string of length N that contains only 4s and 7s. Find the number of balanced strings that can be reached by any permutation of S. A balanced string is a string for which an index x (1-based) exists such that

number of 4s in substring [1, x) = number of 7s in substring (x, N]

Note: We can trivially simplify **“any number of swaps on pairs of consecutive digits”** as given in the problem statement to **“any permutation”**.

# QUICK EXPLANATION

The answer can be found in **O(|s| ^{2})** time for each test case using

**Dynamic Programming**. But there is a much more clever solution! After you precalculate all the binomial coefficients

**for**

^{n}C_{r}**0 ≤ r ≤ n ≤ 5000**you can calculate the answer in

**O(1)**time for each test case!

Alternately, the answer for each test case can be found in **O(|s|)** time.

All the details of the proof below are taken from the notes of Hiroto Sekido that he gave during testing this problem.

# EXPLANATION

Let **S** be the string which is given.

- Let
**N4**be the number of**4s**in**S** - Let
**N7**be the number of**7s**in**S**

**Theorem: S is unbalanced iff S is of the form A + “47” + B, AND |A| = N7-1, AND |B| = N4-1.**

**Proof**

Let us show the **S** of the form as described in the theorem, is indeed **unbalanced.**

- Let
**z**be the number of**4s**in**A** - Number of
**7s**in**A = N7-1 - z**- Since
**|A| = N7-1**

- Since
- Number of
**7s**in**B = z**- Since Number of
**7s**in**B = N7 - (number of 7s in A) - 1 = N7 - N7 + 1 + z - 1 = z**

- Since Number of
- Number of
**4s**in**B = N4-1 - z**- Since
**|B| = N4-1**

- Since

Now, consier **x = N7**

- Number of
**4s**in**[1, x) = z** - Number of
**7s**in**(x, N] = z+1**

Hence, string is not balanced at **x = N7**

Now, consider **x = N7+1**

- Number of
**4s**in**[1, x) = z+1** - Number of
**7s**in**(x, 1] = z**

Hence, string is not balanced at **x = N7+1**

The following insights are trivially observable

**If we increase x, the number of 4s on the left can never decrease.****Similarly, if we increase x, the number of 7s on the right can never increase.**

Corollarly,

**If we decrease x, the number of 4s on the left can never increase.****Similarly, if we decrease x, the number of 7s on the right can never decrease.**

Thus, we make the following conclusions

- In
**S**, for any**x < N7**,**number of 4s in [1, x) < number of 7s in (x, N]**- Since,
**number of 4s in [1, N7) < number of 7s in (N7, N]**

- Since,
- Similarly, for any
**x > N7+1**,**number of 4s in [1, x) > number of 7s in (x, N]**- Since,
**number of 4s in [1, N7+1) > number of 7s in (N7+1, N]**

- Since,

Hence, **S** must be an **unbalanced string**.

But to prove the **if-and-only-if** part of our **Theorem**, we must also prove that any other form of **S** is balanced except the one that satisfies the description in the theorem.

There are **three more** cases that should be proven as **“balanced”** to call the **Theorem** true.

**Case 1: S = A + “44” + B, |A| = N7-1, |B| = N4-1**

- Let
**z**be the number of**4s**in**A** - Number of
**7s**in**A = N7-1 - z** - Number of
**7s**in**B = N7 - (number of 7s in A) = N7 - (N7-1 - z) = z + 1**

Now, at **x = N7+1**

- Number of
**4s**in**[1, x) = z+1** - Number of
**7s**in**(x, N] = z+1**

Hence **S** is **balanced**.

**Case 2: S = A + “77” + B, |A| = N7-1, |B| = N4-1**

- Let
**z**be the number of**4s**in**A** - Number of
**7s**in**A = N7-1 - z - 2** - Number of
**7s**in**B = N7 - (number of 7s in A) - 2 = N7 - (N7-1 - z) - 2 = z - 1**

Now, at **x = N7**

- Number of
**4s**in**[1, x) = z** - Number of
**7s**in**(x, N] = z**

Hence **S** is **balanced**.

**Case 3: S = A + “74” + B, |A| = N7-1, |B| = N4-1**

- Let
**z**be the number of**4s**in**A** - Number of
**7s**in**A = N7-1 - z** - Number of
**7s**in**B = N7 - (number of 7s in A) - 1 = N7 - (N7-1 - z) - 1 = z**

Now, at **x = N7**

- Number of
**4s**in**[1, x) = z** - Number of
**7s**in**(x, N] = z**

Also, at **x = N7+1**

- Number of
**4s**in**[1, x) = z** - Number of
**7s**in**(x, N] = z**

Hence **S** is **balanced**. In fact, we have two evidences this time.

## CONCLUSION

Thus, we have seen that for any string **S** of the type **A + “xx” + B**, where **|A| = N7-1**, **|B| = N4-1**, **S** will be unbalanced **iff “xx” = “47”**.

This is a very strong condition. Every string will have a **unique partition** into an **A** and **B**, and its **balanced-ness** simply depends upon the two characters in between

The answer thus would be

^{N}C_{N4} - ^{N-2}C_{N4-1}

# SETTERS SOLUTION

Can be found here.

# TESTERS SOLUTION

Can be found here.