# Fibonacci String Codechef Solution

For a string SS let the unique set of characters that occur in it one or more times be CC. Consider a permutation of the elements of CC as (c1,c2,c3…)(c1,c2,c3…). Let f(c)f(c) be the number of times cc occurs in SS.

If any such permutation of the elements of CC satisfies f(ci)=f(ci−1)+f(ci−2)f(ci)=f(ci−1)+f(ci−2) for all i≥3i≥3, the string is said to be a dynamic string.

Mr Bancroft is given the task to check if the string is dynamic, but he is busy playing with sandpaper. Would you help him in such a state?

Note that if the number of distinct characters in the string is less than 3, i.e. if |C|<3|C|<3, then the string is always dynamic.

### Input:

• First line will contain TT, number of testcases. Then the testcases follow.
• Each testcase contains of a single line of input, a string SS.

### Output:

For each testcase, output in a single line “Dynamic” if the given string is dynamic, otherwise print “Not“. (Note that the judge is case sensitive)

### Constraints

• 1≤T≤101≤T≤10
• 1≤|S|≤1051≤|S|≤105
• SS contains only lower case alphabets: aa, bb, …, zz

```3
aaaabccc
aabbcc
ppppmmnnoooopp
```

### Sample Output:

```Dynamic
Not
Dynamic
```

### Explanation:

• Testase 1: For the given string, C={a,b,c}C={a,b,c} and f(a)=4,f(b)=1,f(c)=3f(a)=4,f(b)=1,f(c)=3. f(a)=f(c)+f(b)f(a)=f(c)+f(b) so the permutation (b,c,a)(b,c,a) satisfies the requirement.
• Testcase 2: Here too C={a,b,c}C={a,b,c} but no permutation satisfies the requirement of a dynamic string.
• Testcase 3: Here C={m,n,o,p}C={m,n,o,p} and (m,n,o,p)(m,n,o,p) is a permutation that makes it a dynamic string.

## Fibonacci String – CodeChef Solution in JAVA

```import java.util.*;
import java.util.stream.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{

for (int i = 0; i < numberOfInputs; i++) {
}

br.close();
}

private static void determineDynamic(String input) {
char[] charArray = input.toCharArray();

List<Integer> numOfChars = new ArrayList<Integer>();
int currentAmount = 1;

for (int k = 1; k < charArray.length; k++) {
if (charArray[k-1] == charArray[k]) {
currentAmount = currentAmount + 1;
}
else {
currentAmount = 1;
}
}

for (int j = 2; j < numOfChars.size(); j++) {
if (numOfChars.get(j-2) + numOfChars.get(j-1) == numOfChars.get(j) ||
numOfChars.get(j-2) + numOfChars.get(j) == numOfChars.get(j-1) ||
numOfChars.get(j) + numOfChars.get(j-1) == numOfChars.get(j-2)) {
continue;
}
else {
System.out.println("Not");
return;
}
}

System.out.println("Dynamic");
}
}
```

## Fibonacci String – CodeChef Solution in CPP

```#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
int n=s.length();
map<char,int>m;
for(int i=0; i<n; i++)
{
m[s[i]]++;
}
int*arr,j=0;
arr=new int[m.size()];
for(auto it=m.begin(); it!=m.end(); it++)
{
arr[j++]=it->second;

}
sort(arr,arr+j);

if(j<3)
{
cout<<"Dynamic"<<endl;
}
else
{
int f=1;
if(j>3)
{
if(arr[1]+arr[2]!=arr[3])
{
swap(arr[0],arr[1]);
}

}
for(int i=2; i<j; i++)
{
if(arr[i]!=arr[i-1]+arr[i-2])
{
f=0;
break;
}
}
if(f==1)
{
cout<<"Dynamic"<<endl;
}
else
{
cout<<"Not"<<endl;
}

}
}
return 0;
}
```

## Fibonacci String   -CodeChef Solution in Python

```for _ in range(int(input())):
a=input()
b=[a.count(i) for i in set(a)]
b.sort()
if(len(b)<3):
print('Dynamic')
continue
if(b[-3]+b[-2]!=b[-1]):
print('Not')
continue
else:
print('Dynamic')```

Disclaimer: The above Problem (Fibonacci String ) is generated by CodeChef but the solution is provided by Codeworld19.This tutorial is only for Educational and Learning purpose.