Strings formadas a partir de caracteres dados sin caracteres repetidos consecutivos

Dada una array de strings arr[] y una string str , la tarea es imprimir todas las strings de la array arr que siguen las siguientes condiciones: 

• Las strings resultantes no deben contener ningún carácter repetido consecutivo.
• Las strings resultantes deben formarse usando solo los caracteres de la string str .

Ejemplos:  

Entrada: arr[] = { “AABCDA”, “ABCDZADC”, “ABCDBCA”, “ABCDABDCA” }, str = “ADCB” 
Salida: ABCDABDCA ABCDBCA

Entrada: arr[] = { “A”, “B”, “AB”, “ACB” }, str = “AB” 
Salida: AB AB 

Enfoque: la idea es iterar a través de la array y para cada string, verificar si contiene caracteres repetidos consecutivos y cualquier otro carácter que no sea el mencionado en la string str . Si se cumple cualquiera de las condiciones anteriores, continúe revisando la siguiente string. De lo contrario, imprima la string.
A continuación se muestra la implementación del enfoque anterior:

// CPP implementation of the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to check whether the string contains
// any consecutive repetitive characters
// and any characters other than those in str
bool check(string s, string str)
{
    string chars = s;
     
    set<char> st;
    // Valid characters check
    for(int i = 0; i < str.length(); i++)
        st.insert(str[i]);
    for (char c : chars) {
        if(st.find(c) == st.end())
        return false;
    }
 
    // Nonrepetitive check
    for (int i = 0; i < chars.length() - 1; i++) {
        if (chars[i] == chars[i + 1]) {
            return false;
        }
    }
    return true;
}
     
     
// Function to print the strings which
// satisfy the mentioned conditions
void getStrings(string str, vector<string> arr)
{
    // Iterate through all the strings
    // in the array.
    for (int i = 0; i <arr.size(); i++) {
 
        // check function to check the
        // conditions for every string
        if (check(arr[i], str)) {
            cout<<arr[i]<<" ";
        }
    }
}
 
// Driver code
int main()
{
    string str = "ABCD";
    vector<string> arr({"AABCDA", "ABCDZADC","ABCDBCA", "ABCDABDCA"});
    getStrings(str, arr);
}
 
// This code is contributed by Surendra_Gangwar

// Java implementation of the above approach
import java.util.*;
 
public class GFG {
 
    // Function to print the strings which
    // satisfy the mentioned conditions
    public static void getStrings(
        String str, String[] arr)
    {
        // Iterate through all the strings
        // in the array.
        for (int i = 0; i < arr.length; i++) {
 
            // check function to check the
            // conditions for every string
            if (check(arr[i], str)) {
                System.out.print(arr[i] + " ");
            }
        }
    }
 
    // Function to check whether the string contains
    // any consecutive repetitive characters
    // and any characters other than those in str
    public static boolean check(String s, String str)
    {
        char[] chars = s.toCharArray();
 
        // Valid characters check
        for (char c : chars) {
            if (!str.contains(String.valueOf(c))) {
                return false;
            }
        }
 
        // Nonrepetitive check
        for (int i = 0; i < chars.length - 1; i++) {
            if (chars[i] == chars[i + 1]) {
                return false;
            }
        }
        return true;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String str = "ABCD";
        String[] arr
            = { "AABCDA", "ABCDZADC",
                "ABCDBCA", "ABCDABDCA" };
        getStrings(str, arr);
    }
}

# Python3 implementation of the above approach
# Function to print the strings which
# satisfy the mentioned conditions
 
def getStrings(strr, arr):
     
    # Iterate through all the strings
    # in the array.
    for i in range(len(arr)):
         
        # check function to check the
        # conditions for every string
        if (check(arr[i], strr)):
            print(arr[i],end=" ")
             
# Function to check whether the string contains
# any consecutive repetitive characters
# and any characters other than those in str
def check(s, strr):
     
    chars = s
     
    # Valid characters check
    for c in chars:
         
        if c not in strr:
            return False
             
    # Nonrepetitive check
    for i in range(len(chars)-1):
        if (chars[i] == chars[i + 1]):
            return False
     
    return True
 
# Driver code
 
strr = "ABCD"
arr = ["AABCDA", "ABCDZADC","ABCDBCA", "ABCDABDCA"]
getStrings(strr, arr)
 
# This code is contributed by shubhamsingh10

// C# implementation of the above approach
using System;
 
class GFG {
  
    // Function to print the strings which
    // satisfy the mentioned conditions
    public static void getStrings(
        String str, String[] arr)
    {
        // Iterate through all the strings
        // in the array.
        for (int i = 0; i < arr.Length; i++) {
  
            // check function to check the
            // conditions for every string
            if (check(arr[i], str)) {
                Console.Write(arr[i] + " ");
            }
        }
    }
  
    // Function to check whether the string contains
    // any consecutive repetitive characters
    // and any characters other than those in str
    public static bool check(String s, String str)
    {
        char[] chars = s.ToCharArray();
  
        // Valid characters check
        foreach (char c in chars) {
            if (!str.Contains(String.Join("",c))) {
                return false;
            }
        }
  
        // Nonrepetitive check
        for (int i = 0; i < chars.Length - 1; i++) {
            if (chars[i] == chars[i + 1]) {
                return false;
            }
        }
        return true;
    }
  
    // Driver code
    public static void Main(String[] args)
    {
        String str = "ABCD";
        String[] arr
            = { "AABCDA", "ABCDZADC",
                "ABCDBCA", "ABCDABDCA" };
        getStrings(str, arr);
    }
}
 
// This code is contributed by 29AjayKumar

<script>
// Javascript implementation of the above approach
 
// Function to check whether the string contains
// any consecutive repetitive characters
// and any characters other than those in str
function check(s, str)
{
    let chars = s;
     
    let st = new Set();
    // Valid characters check
    for(let i = 0; i < str.length; i++)
        st.add(str[i]);
    for (let c of chars) {
        if(!st.has(c))
        return false;
    }
 
    // Nonrepetitive check
    for (let i = 0; i < chars.length - 1; i++) {
        if (chars[i] == chars[i + 1]) {
            return false;
        }
    }
    return true;
}
     
     
// Function to print the strings which
// satisfy the mentioned conditions
function getStrings(str, arr)
{
    // Iterate through all the strings
    // in the array.
    for (let i = 0; i < arr.length; i++) {
 
        // check function to check the
        // conditions for every string
        if (check(arr[i], str)) {
            document.write(arr[i] + " ");
        }
    }
}
 
// Driver code
 
let str = "ABCD";
let arr = new Array("AABCDA", "ABCDZADC","ABCDBCA", "ABCDABDCA");
getStrings(str, arr);
 
// This code is contributed by _saurabh_jaiswal
</script>

ABCDBCA ABCDABDCA

Complejidad de tiempo: O(m * n), donde n es el tamaño de la array (vector) de strings y m es la longitud máxima de una string en el vector.

Espacio auxiliar: O(N), donde N es el tamaño de la string dada.