Check whether frequency of characters in a string makes Fibonacci Sequence | C ++ program to check whether frequency of characters in a string makes Fibonacci Sequence ; Function to check if the frequencies are in Fibonacci series ; map to store the frequencies of character ; Vector to store first n fibonacci numbers ; Get the size of the map ; a and b are first and second terms of fibonacci series ; vector v contains elements of fibonacci series ; Compare vector elements with values in Map ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; string isFibonacci ( string s ) { map < char , int > m ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { m [ s [ i ] ] ++ ; } vector < int > v ; int n = m . size ( ) ; int a = 1 , b = 1 ; int c ; v . push_back ( a ) ; v . push_back ( b ) ; for ( int i = 0 ; i < n - 2 ; i ++ ) { v . push_back ( a + b ) ; c = a + b ; a = b ; b = c ; } int flag = 1 ; int i = 0 ; for ( auto itr = m . begin ( ) ; itr != m . end ( ) ; itr ++ ) { if ( itr -> second != v [ i ] ) { flag = 0 ; break ; } i ++ ; } if ( flag == 1 ) return " YES " ; else return " NO " ; } int main ( ) { string s = " abeeedd " ; cout << isFibonacci ( s ) ; return 0 ; }