Dadas duas strings, imprima todos os caracteres comuns em lexicográfico ordem. Se não houver letras comuns, imprima -1. Todas as letras são minúsculas.
Exemplos:
Input : string1 : geeks string2 : forgeeks Output : eegks Explanation: The letters that are common between the two strings are e(2 times) k(1 time) and s(1 time). Hence the lexicographical output is 'eegks' Input : string1 : hhhhhello string2 : gfghhmh Output : hhh
A ideia é usar matrizes de contagem de caracteres.
- Conte as ocorrências de todos os caracteres de 'a' a 'z' na primeira e na segunda strings. Armazene essas contagens em duas matrizes a1[] e a2[].
- Percorra a1[] e a2[] (observe que o tamanho de ambos é 26). Para cada índice imprimo o caractere 'a' + i número de vezes igual a min (a1[i] a2[i]).
Abaixo está a implementação das etapas acima.
C++// C++ program to print common characters // of two Strings in alphabetical order #include using namespace std; int main() { string s1 = 'geeksforgeeks'; string s2 = 'practiceforgeeks'; // to store the count of // letters in the first string int a1[26] = {0}; // to store the count of // letters in the second string int a2[26] = {0}; int i j; char ch; char ch1 = 'a'; int k = (int)ch1 m; // for each letter present increment the count for(i = 0 ; i < s1.length() ; i++) { a1[(int)s1[i] - k]++; } for(i = 0 ; i < s2.length() ; i++) { a2[(int)s2[i] - k]++; } for(i = 0 ; i < 26 ; i++) { // the if condition guarantees that // the element is common that is // a1[i] and a2[i] are both non zero // means that the letter has occurred // at least once in both the strings if (a1[i] != 0 and a2[i] != 0) { // print the letter for a number // of times that is the minimum // of its count in s1 and s2 for(j = 0 ; j < min(a1[i] a2[i]) ; j++) { m = k + i; ch = (char)(k + i); cout << ch; } } } return 0; }
Java // Java program to print common characters // of two Strings in alphabetical order import java.io.*; import java.util.*; // Function to find similar characters public class Simstrings { static final int MAX_CHAR = 26; static void printCommon(String s1 String s2) { // two arrays of length 26 to store occurrence // of a letters alphabetically for each string int[] a1 = new int[MAX_CHAR]; int[] a2 = new int[MAX_CHAR]; int length1 = s1.length(); int length2 = s2.length(); for (int i = 0 ; i < length1 ; i++) a1[s1.charAt(i) - 'a'] += 1; for (int i = 0 ; i < length2 ; i++) a2[s2.charAt(i) - 'a'] += 1; // If a common index is non-zero it means // that the letter corresponding to that // index is common to both strings for (int i = 0 ; i < MAX_CHAR ; i++) { if (a1[i] != 0 && a2[i] != 0) { // Find the minimum of the occurrence // of the character in both strings and print // the letter that many number of times for (int j = 0 ; j < Math.min(a1[i] a2[i]) ; j++) System.out.print(((char)(i + 'a'))); } } } // Driver code public static void main(String[] args) throws IOException { String s1 = 'geeksforgeeks' s2 = 'practiceforgeeks'; printCommon(s1 s2); } }
Python3 # Python3 program to print common characters # of two Strings in alphabetical order # Initializing size of array MAX_CHAR=26 # Function to find similar characters def printCommon( s1 s2): # two arrays of length 26 to store occurrence # of a letters alphabetically for each string a1 = [0 for i in range(MAX_CHAR)] a2 = [0 for i in range(MAX_CHAR)] length1 = len(s1) length2 = len(s2) for i in range(0length1): a1[ord(s1[i]) - ord('a')] += 1 for i in range(0length2): a2[ord(s2[i]) - ord('a')] += 1 # If a common index is non-zero it means # that the letter corresponding to that # index is common to both strings for i in range(0MAX_CHAR): if (a1[i] != 0 and a2[i] != 0): # Find the minimum of the occurrence # of the character in both strings and print # the letter that many number of times for j in range(0min(a1[i]a2[i])): ch = chr(ord('a')+i) print (ch end='') # Driver code if __name__=='__main__': s1 = 'geeksforgeeks' s2 = 'practiceforgeeks' printCommon(s1 s2); # This Code is contributed by Abhishek Sharma
C# // C# program to print common characters // of two Strings in alphabetical order using System; // Function to find similar characters public class Simstrings { static int MAX_CHAR = 26; static void printCommon(string s1 string s2) { // two arrays of length 26 to store occurrence // of a letters alphabetically for each string int[] a1 = new int[MAX_CHAR]; int[] a2 = new int[MAX_CHAR]; int length1 = s1.Length; int length2 = s2.Length; for (int i = 0 ; i < length1 ; i++) a1[s1[i] - 'a'] += 1; for (int i = 0 ; i < length2 ; i++) a2[s2[i] - 'a'] += 1; // If a common index is non-zero it means // that the letter corresponding to that // index is common to both strings for (int i = 0 ; i < MAX_CHAR ; i++) { if (a1[i] != 0 && a2[i] != 0) { // Find the minimum of the occurrence // of the character in both strings and print // the letter that many number of times for (int j = 0 ; j < Math.Min(a1[i] a2[i]) ; j++) Console.Write(((char)(i + 'a'))); } } } // Driver code public static void Main() { string s1 = 'geeksforgeeks' s2 = 'practiceforgeeks'; printCommon(s1 s2); } }
JavaScript <script> // Javascript program to print common characters // of two Strings in alphabetical order let MAX_CHAR = 26; // Function to find similar characters function printCommon(s1s2) { // two arrays of length 26 to store occurrence // of a letters alphabetically for each string let a1 = new Array(MAX_CHAR); let a2 = new Array(MAX_CHAR); for(let i=0;i<MAX_CHAR;i++) { a1[i]=0; a2[i]=0; } let length1 = s1.length; let length2 = s2.length; for (let i = 0 ; i < length1 ; i++) a1[s1[i].charCodeAt(0) - 'a'.charCodeAt(0)] += 1; for (let i = 0 ; i < length2 ; i++) a2[s2[i].charCodeAt(0) - 'a'.charCodeAt(0)] += 1; // If a common index is non-zero it means // that the letter corresponding to that // index is common to both strings for (let i = 0 ; i < MAX_CHAR ; i++) { if (a1[i] != 0 && a2[i] != 0) { // Find the minimum of the occurrence // of the character in both strings and print // the letter that many number of times for (let j = 0 ; j < Math.min(a1[i] a2[i]) ; j++) document.write((String.fromCharCode(i + 'a'.charCodeAt(0)))); } } } // Driver code let s1 = 'geeksforgeeks' s2 = 'practiceforgeeks'; printCommon(s1 s2); // This code is contributed by avanitrachhadiya2155 </script>
Saída
eeefgkors
Complexidade de tempo: Se considerarmos n = comprimento (string maior), então este algoritmo é executado em Sobre) complexidade.
Espaço Auxiliar: O(1).