РАЗЛИЧНИ НИЗОВЕ С РАЗРЕШЕНИ НЕЧЕТНИ И ЧЕТНИ ПРОМЕНИ

Като се има предвид масив от низове с малки букви, задачата е да се намери броя на низовете, които са различни. Два низа са различни, ако при прилагане на следните операции върху един низ вторият низ не може да бъде образуван.

Символ с нечетен индекс може да бъде заменен само с друг знак с нечетен индекс.
Символ с четен индекс може да бъде разменен с друг знак само с четен индекс.

Примери:

Input : arr[] = {'abcd' 'cbad' 'bacd'} Output : 2 The 2nd string can be converted to the 1st by swapping the first and third characters. So there are 2 distinct

strings as the third string cannot be converted to the first. Input : arr[] = {'abc' 'cba'} Output : 1

А просто решение е да стартирате два цикъла. Външният цикъл избира низ, а вътрешният цикъл проверява дали има предишен низ, който може да бъде преобразуван в текущ низ чрез извършване на разрешени трансформации. Това решение изисква O(n²m) време, където n е броят на низовете, а m е максималният брой знаци във всеки низ.

Ан ефикасно решение генерира кодиран низ за всеки входен низ. Кодираният има брой четни и нечетни позиционирани знаци, разделени с разделител. Два низа се считат за еднакви, ако техните кодирани низове са еднакви, а иначе не. След като имаме начин да кодираме низове, проблемът се свежда до преброяване на различни кодирани низове. Това е типичен проблем на хеширането. Ние създаваме хеш набор и един по един съхраняваме кодировки на низове. Ако вече съществува кодиране, ние игнорираме низа. В противен случай съхраняваме кодирането в хеш и увеличаваме броя на различни низове.

Изпълнение:

C++

#include   using namespace std; int MAX_CHAR = 26; string encodeString(char str[] int m) {  // hashEven stores the count of even indexed character  // for each string hashOdd stores the count of odd  // indexed characters for each string  int hashEven[MAX_CHAR];  int hashOdd[MAX_CHAR];  memset(hashEven0sizeof(hashEven));  memset(hashOdd0sizeof(hashOdd));  // creating hash for each string  for (int i = 0; i < m; i++) {  char c = str[i];  if ((i & 1) != 0) // If index of current character is odd  hashOdd[c-'a']++;  else  hashEven[c-'a']++;  }  // For every character from 'a' to 'z' we store its  // count at even position followed by a separator  // followed by count at odd position.  string encoding = '';  for (int i = 0; i < MAX_CHAR; i++) {  encoding += (hashEven[i]);  encoding += ('-');  encoding += (hashOdd[i]);  encoding += ('-');  }  return encoding; } // This function basically uses a hashing based set to // store strings which are distinct according // to criteria given in question. int countDistinct(string input[] int n) {  int countDist = 0; // Initialize result  // Create an empty set and store all distinct  // strings in it.  set<string> s;  for (int i = 0; i < n; i++) {  // If this encoding appears first time increment  // count of distinct encodings.  char char_array[input[i].length()];  strcpy(char_array input[i].c_str());  if (s.find(encodeString(char_array input[i].length())) == s.end()) {  s.insert(encodeString(char_arrayinput[i].length()));  countDist++;  }  }  return countDist; } int main() {  string input[] = {'abcd' 'acbd' 'adcb' 'cdba'  'bcda' 'badc'};  int n = sizeof(input)/sizeof(input[0]);  cout << countDistinct(input n) << 'n'; } // This code is contributed by Harshit Sharma.

Java

// Java program to count distinct strings with // even odd swapping allowed. import java.util.HashSet; import java.util.Set; class GFG { static int MAX_CHAR = 26;  static String encodeString(char[] str) {  // hashEven stores the count of even indexed character  // for each string hashOdd stores the count of odd  // indexed characters for each string  int hashEven[] = new int[MAX_CHAR];  int hashOdd[] = new int[MAX_CHAR];  // creating hash for each string  for (int i = 0; i < str.length; i++) {  char c = str[i];  if ((i & 1) != 0) // If index of current character is odd  hashOdd[c-'a']++;  else  hashEven[c-'a']++;  }  // For every character from 'a' to 'z' we store its  // count at even position followed by a separator  // followed by count at odd position.  String encoding = '';  for (int i = 0; i < MAX_CHAR; i++) {  encoding += (hashEven[i]);  encoding += ('-');  encoding += (hashOdd[i]);  encoding += ('-');  }  return encoding;  }  // This function basically uses a hashing based set to // store strings which are distinct according // to criteria given in question.  static int countDistinct(String input[] int n) {  int countDist = 0; // Initialize result  // Create an empty set and store all distinct  // strings in it.  Set<String> s = new HashSet<>();  for (int i = 0; i < n; i++) {  // If this encoding appears first time increment  // count of distinct encodings.  if (!s.contains(encodeString(input[i].toCharArray()))) {  s.add(encodeString(input[i].toCharArray()));  countDist++;  }  }  return countDist;  }  public static void main(String[] args) {  String input[] = {'abcd' 'acbd' 'adcb' 'cdba'  'bcda' 'badc'};  int n = input.length;  System.out.println(countDistinct(input n));  } }

Python3

# Python3 program to count distinct strings with # even odd swapping allowed. MAX_CHAR = 26 # Returns encoding of string that can be used  # for hashing. The idea is to return same encoding  # for strings which can become same after swapping  # a even positioned character with other even characters  # OR swapping an odd character with other odd characters. def encodeString(string): # hashEven stores the count of even indexed character # for each string hashOdd stores the count of odd # indexed characters for each string hashEven = [0] * MAX_CHAR hashOdd = [0] * MAX_CHAR # creating hash for each string for i in range(len(string)): c = string[i] if i & 1: # If index of current character is odd hashOdd[ord(c) - ord('a')] += 1 else: hashEven[ord(c) - ord('a')] += 1 # For every character from 'a' to 'z' we store its # count at even position followed by a separator # followed by count at odd position. encoding = '' for i in range(MAX_CHAR): encoding += str(hashEven[i]) encoding += str('-') encoding += str(hashOdd[i]) encoding += str('-') return encoding # This function basically uses a hashing based set to # store strings which are distinct according # to criteria given in question. def countDistinct(input n): countDist = 0 # Initialize result # Create an empty set and store all distinct # strings in it. s = set() for i in range(n): # If this encoding appears first time increment # count of distinct encodings. if encodeString(input[i]) not in s: s.add(encodeString(input[i])) countDist += 1 return countDist # Driver Code if __name__ == '__main__': input = ['abcd' 'acbd' 'adcb' 'cdba' 'bcda' 'badc'] n = len(input) print(countDistinct(input n)) # This code is contributed by # sanjeev2552

// C# program to count distinct strings with // even odd swapping allowed. using System; using System.Collections.Generic;    class GFG {  static int MAX_CHAR = 26;  static String encodeString(char[] str)   {  // hashEven stores the count of even   // indexed character for each string   // hashOdd stores the count of odd  // indexed characters for each string  int []hashEven = new int[MAX_CHAR];  int []hashOdd = new int[MAX_CHAR];  // creating hash for each string  for (int i = 0; i < str.Length; i++)   {  char m = str[i];    // If index of current character is odd  if ((i & 1) != 0)   hashOdd[m - 'a']++;  else  hashEven[m - 'a']++;  }  // For every character from 'a' to 'z'   // we store its count at even position   // followed by a separator   // followed by count at odd position.  String encoding = '';  for (int i = 0; i < MAX_CHAR; i++)   {  encoding += (hashEven[i]);  encoding += ('-');  encoding += (hashOdd[i]);  encoding += ('-');  }  return encoding;  }  // This function basically uses a hashing based set  // to store strings which are distinct according   // to criteria given in question.  static int countDistinct(String []input int n)   {  int countDist = 0; // Initialize result  // Create an empty set and store all distinct  // strings in it.  HashSet<String> s = new HashSet<String>();  for (int i = 0; i < n; i++)   {  // If this encoding appears first time  // increment count of distinct encodings.  if (!s.Contains(encodeString(input[i].ToCharArray())))   {  s.Add(encodeString(input[i].ToCharArray()));  countDist++;  }  }  return countDist;  }  // Driver Code  public static void Main(String[] args)   {  String []input = {'abcd' 'acbd' 'adcb'   'cdba' 'bcda' 'badc'};  int n = input.Length;  Console.WriteLine(countDistinct(input n));  } } // This code is contributed by 29AjayKumar

JavaScript

<script>  // Javascript program to count distinct strings with  // even odd swapping allowed  let MAX_CHAR = 26;    function encodeString(str) {  // hashEven stores the count of even indexed character  // for each string hashOdd stores the count of odd  // indexed characters for each string  let hashEven = Array(MAX_CHAR).fill(0);  let hashOdd = Array(MAX_CHAR).fill(0);    // creating hash for each string  for (let i = 0; i < str.length; i++) {  let c = str[i];  if ((i & 1) != 0) // If index of current character is odd  hashOdd[c.charCodeAt() - 'a'.charCodeAt()]++;  else  hashEven[c.charCodeAt() - 'a'.charCodeAt()]++;    }      // For every character from 'a' to 'z' we store its  // count at even position followed by a separator  // followed by count at odd position.  let encoding = '';  for (let i = 0; i < MAX_CHAR; i++) {  encoding += (hashEven[i]);  encoding += ('-');  encoding += (hashOdd[i]);  encoding += ('-');  }  return encoding;  }    // This function basically uses a hashing based set to  // store strings which are distinct according  // to criteria given in question.  function countDistinct(input n) {  let countDist = 0; // Initialize result    // Create an empty set and store all distinct  // strings in it.  let s = new Set();  for (let i = 0; i < n; i++) {  // If this encoding appears first time increment  // count of distinct encodings.  if (!s.has(encodeString(input[i].split('')))) {  s.add(encodeString(input[i].split('')));  countDist++;  }  }    return countDist;  } // Driver program   let input = ['abcd' 'acbd' 'adcb' 'cdba'  'bcda' 'badc'];  let n = input.length;    document.write(countDistinct(input n)); </script>

Изход

Времева сложност : O(n)
Помощно пространство: O(1)

Създаване на тест

TechCodeview

Различни низове с разрешени нечетни и четни промени