Check whether frequency of characters in a string makes Fibonacci Sequence | Python3 program to check whether the frequency of characters in a string make 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
from collections import defaultdict NEW_LINE def isFibonacci ( s ) : NEW_LINE INDENT m = defaultdict ( lambda : 0 ) NEW_LINE for i in range ( 0 , len ( s ) ) : NEW_LINE INDENT m [ s [ i ] ] += 1 NEW_LINE DEDENT v = [ ] NEW_LINE n = len ( m ) NEW_LINE a = b = 1 NEW_LINE v . append ( a ) NEW_LINE v . append ( b ) NEW_LINE for i in range ( 0 , n - 2 ) : NEW_LINE INDENT v . append ( a + b ) NEW_LINE c = a + b NEW_LINE a , b = b , c NEW_LINE DEDENT flag , i = 1 , 0 NEW_LINE for itr in sorted ( m ) : NEW_LINE INDENT if m [ itr ] != v [ i ] : NEW_LINE INDENT flag = 0 NEW_LINE break NEW_LINE DEDENT i += 1 NEW_LINE DEDENT if flag == 1 : NEW_LINE INDENT return " YES " NEW_LINE DEDENT else : NEW_LINE INDENT return " NO " NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " abeeedd " NEW_LINE print ( isFibonacci ( s ) ) NEW_LINE DEDENT