String con frecuencia de caracteres en Lucas Sequence

Dada una string ‘str’ que contiene alfabetos ingleses en minúsculas, la tarea es encontrar si las frecuencias de los caracteres de la string están en secuencia de Lucas o no. Usted es libre de ordenar los números de frecuencia de cualquier forma para formar la secuencia de Lucas. Si es posible, escriba SÍ ; de lo contrario , NO .

Secuencia Lucas .

Nota: Se deben usar todas las frecuencias para verificar si están en la Secuencia de Lucas.

Ejemplos:

Entrada: str = “gggeek”
Salida: SÍ
frecuencia de ‘g’ = 3
frecuencia de ‘e’ = 2
frecuencia de ‘k’ = 1
Estas frecuencias se pueden organizar para formar los primeros 3 términos de la secuencia de Lucas, {2, 1, 3}.

Entrada: str = «geeksforgeeks»
Salida: NO

Acercarse:

• Almacene la frecuencia de cada carácter en un vector usando el mapa STL . Ordenar el vector después.
• Cambie el primer y segundo elemento del primer vector a ‘2’ y ‘1’ respectivamente, ya que la secuencia de Lucas tiene ‘2’ y ‘1’ como los dos primeros números. Sin embargo, el cambio solo debe realizarse si ‘1’ y ‘2’ están presentes en el vector. Si no está presente, entonces las frecuencias nunca pueden estar en secuencia de Lucas y generar NO.
• Luego, haz otro vector. Sea n el tamaño del primer vector.
• Inserte los primeros números ‘n’ Lucas en el segundo vector.
• Luego, compare cada elemento en ambos vectores. Si ambos vectores son iguales, emite ‘SÍ’, de lo contrario, emite ‘NO’.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of
// the approach
#include <bits/stdc++.h>
using namespace std;
  
// function that checks
// if the frequencies
// are in Lucas sequence.
string lucas_sequence(string s, int n)
{
    // map is used to store
    // character frequencies
    map<char, int> m;
    for (int i = 0; i < n; i++) {
        if (m.find(s[i]) == m.end())
            m[s[i]] = 1;
        else
            m[s[i]]++;
    }
  
    vector<int> v1, v2;
  
    map<char, int>::iterator it;
  
    // frequencies are extracted from
    // map and stored in vector v1
    for (it = m.begin(); it != m.end(); it++)
        v1.push_back((*it).second);
  
    // vector v1 elements are sorted,
    // but first and second element are
    // changed to '2' and '1' respectively,
    // only if '1' and '2' are present in the vector.
    sort(v1.begin(), v1.end());
    if (v1[0] == 1 && v1[1] == 2) {
        v1[0] = 2;
        v1[1] = 1;
    }
    else
        return "NO";
  
    // a and b are first and
    // second terms of
    // Lucas sequence
    int a = 2, b = 1;
    int c;
    v2.push_back(a);
    v2.push_back(b);
  
    // v2 contains Lucas sequence
    for (int i = 0; i < v1.size() - 2; i++) {
        v2.push_back(a + b);
        c = a + b;
        a = b;
        b = c;
    }
    int flag = 1;
  
    // both vectors are compared
    for (int i = 0; i < v1.size(); i++) {
        if (v1[i] != v2[i]) {
            flag = 0;
            break;
        }
    }
  
    if (flag == 1)
        return "YES";
    else
        return "NO";
}
  
// Driver code
int main()
{
    string s = "oooeeeeqkk";
    int n = s.length();
    cout << lucas_sequence(s, n);
    return 0;
}

// Java implementation of the approach 
import java.util.Collections;
import java.util.HashMap;
import java.util.Vector;
  
class GFG 
{
  
    // function that checks
    // if the frequencies
    // are in Lucas sequence.
    static String lucas_sequence(String s, 
                                 int n) 
    {
  
        // map is used to store
        // character frequencies
        HashMap<Character, 
                Integer> m = new HashMap<>();
        for (int i = 0; i < n; i++)
            m.put(s.charAt(i), 
            m.get(s.charAt(i)) == null ? 1 : 
            m.get(s.charAt(i)) + 1);
  
        Vector<Integer> v1 = new Vector<>();
        Vector<Integer> v2 = new Vector<>();
  
        // frequencies are extracted from
        // map and stored in vector v1
        for (HashMap.Entry<Character, 
                           Integer> entry : m.entrySet())
            v1.add(entry.getValue());
  
        // vector v1 elements are sorted,
        // but first and second element are
        // changed to '2' and '1' respectively,
        // only if '1' and '2' are present in the vector.
        Collections.sort(v1);
        if (v1.elementAt(0) == 1 &&
            v1.elementAt(1) == 2) 
        {
            v1.set(0, 2);
            v1.set(1, 1);
        } 
        else
            return "NO";
  
        // a and b are first and
        // second terms of
        // Lucas sequence
        int a = 2, b = 1;
        int c;
        v2.add(a);
        v2.add(b);
  
        // v2 contains Lucas sequence
        for (int i = 0; i < v1.size() - 2; i++)
        {
            v2.add(a + b);
            c = a + b;
            a = b;
            b = c;
        }
        int flag = 1;
  
        // both vectors are compared
        for (int i = 0; i < v1.size(); i++) 
        {
            if (v1.elementAt(i) != v2.elementAt(i))
            {
                flag = 0;
                break;
            }
        }
  
        if (flag == 1)
            return "YES";
        else
            return "NO";
    }
  
    // Driver Code
    public static void main(String[] args) 
    {
        String s = "oooeeeeqkk";
        int n = s.length();
        System.out.println(lucas_sequence(s, n));
    }
}
  
// This code is contributed by
// sanjeev2552

# Python3 implementation of the approach 
from collections import defaultdict
  
# Function that checks if the 
# frequencies are in Lucas sequence. 
def lucas_sequence(s, n): 
  
    # map is used to store 
    # character frequencies 
    m = defaultdict(lambda:0)
      
    for i in range(0, n): 
        m[s[i]] += 1    
  
    v1, v2 = [], [] 
  
    # frequencies are extracted from 
    # map and stored in vector v1 
    for it in m: 
        v1.append(m[it]) 
  
    # vector v1 elements are sorted, but
    # first and second element are changed 
    # to '2' and '1' respectively, only if 
    # '1' and '2' are present in the vector. 
    v1.sort() 
    if v1[0] == 1 and v1[1] == 2: 
        v1[0], v1[1] = 2, 1
      
    else:
        return "NO"
  
    # a and b are first and second terms 
    # of Lucas sequence 
    a, b = 2, 1
    v2.append(a) 
    v2.append(b) 
  
    # v2 contains Lucas sequence 
    for i in range(0, len(v1) - 2): 
        v2.append(a + b) 
        a, b = b, a + b 
      
    flag = 1
  
    # both vectors are compared 
    for i in range(0, len(v1)): 
        if v1[i] != v2[i]: 
            flag = 0
            break
  
    if flag == 1: 
        return "YES"
    else:
        return "NO"
  
# Driver code 
if __name__ == "__main__":
  
    s = "oooeeeeqkk"
    n = len(s) 
    print(lucas_sequence(s, n)) 
  
# This code is contributed by Rituraj Jain

// C# implementation of the approach
using System;
using System.Collections.Generic; 
  
class GFG 
{
  
    // function that checks
    // if the frequencies
    // are in Lucas sequence.
    static String lucas_sequence(String s, 
                                 int n) 
    {
  
        // map is used to store
        // character frequencies
        Dictionary<char,
                   int> m = new Dictionary<char, 
                                           int>();
        for (int i = 0; i < n; i++)
        {
            if(m.ContainsKey(s[i]))
            {
                m[s[i]] = m[s[i]] + 1;
            }
            else
            {
                m.Add(s[i], 1);
            }
        }
        List<int> v1 = new List<int>();
        List<int> v2 = new List<int>();
  
        // frequencies are extracted from
        // map and stored in vector v1
        foreach(KeyValuePair<char,
                             int> entry in m)
            v1.Add(entry.Value);
  
        // vector v1 elements are sorted,
        // but first and second element are
        // changed to '2' and '1' respectively,
        // only if '1' and '2' are present in the vector.
        v1.Sort();
        if (v1[0] == 1 &&
            v1[1] == 2) 
        {
            v1[0] = 2;
            v1[1] = 1;
        } 
        else
            return "NO";
  
        // a and b are first and
        // second terms of
        // Lucas sequence
        int a = 2, b = 1;
        int c;
        v2.Add(a);
        v2.Add(b);
  
        // v2 contains Lucas sequence
        for (int i = 0; i < v1.Count - 2; i++)
        {
            v2.Add(a + b);
            c = a + b;
            a = b;
            b = c;
        }
        int flag = 1;
  
        // both vectors are compared
        for (int i = 0; i < v1.Count; i++) 
        {
            if (v1[i] != v2[i])
            {
                flag = 0;
                break;
            }
        }
  
        if (flag == 1)
            return "YES";
        else
            return "NO";
    }
  
    // Driver Code
    public static void Main(String[] args) 
    {
        String s = "oooeeeeqkk";
        int n = s.Length;
        Console.WriteLine(lucas_sequence(s, n));
    }
}
  
// This code is contributed by Rajput-Ji

YES