Преобразование строки, которая является повторением подстроки длины K  


Сложный уровень средний
Часто спрашивают в Accenture саман American Express Databricks Свободный заряд
Hash хеширования HashMap строка

Постановка задачи  

В задаче «Преобразование строки, являющейся повторением подстроки длины K» мы задали строка «S» и целое число «k». Напишите программу, чтобы проверить, можно ли преобразовать ее в строку, которая является повторением подстроки с k символами.

Формат ввода  

Первая строка содержит строку «s».

Вторая строка содержит целое значение «k».

Формат вывода  

Выведите «YES», если возможно преобразовать его в строку, являющуюся повторением подстроки с k символами. В противном случае выведите «NO».

ограничения  

  • 1 <= | s | <= 10 ^ 6
  • s [i] должен быть строчными буквами английского алфавита.

Пример  

abcdefabc
3
YES

Объяснение: Здесь мы можем заменить def на abc. Тогда наша обновленная строка s будет «abcabcabc». Теперь мы можем легко увидеть, если мы объединим abc три раза, то получим эту строку.

acdaacda
2
NO

Объяснение: Не существует подстроки длины 2, которую можно было бы заменить и сформировать так, чтобы получить ее путем конкатенации подстроки длины k.

Алгоритм  

1. Пройдите по строке и создайте карту, содержащую частоту подстрок (от 0 до k-1, от k до 2k-1, от 2k до 3k-1 и т. Д.) Длины k.maps strings длины k.

2. Если есть только две разные подстроки длины k и счетчик одной из подстрок равен 1, то выведите «YES».

Смотрите также
Самая длинная подстрока без повторяющихся символов

3. В противном случае выведите «NO».

Реализация  

Программа на C ++ для преобразования строки, которая является повторением подстроки длины K

#include<bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
    string s;
    cin>>s;
    int k;
    cin>>k;
    int n=s.length();
    if(n%k!=0)
    {
        cout<<"NO"<<endl;
    }
    else
    {
        unordered_map<string, int> m; 
        for (int i=0; i<n; i+=k) 
        {
            m[s.substr(i, k)]++;
        }
        if(m.size()==1)
        {
            cout<<"YES"<<endl;
        }
        else if(m.size()==2)
        {
            if(m.begin()->second==1 || m.begin()->second==(n/k-1))
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    return 0; 
}

Программа на Java для преобразования строки, которая является повторением подстроки длины K

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class sum
{ 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                int k = sr.nextInt();
                int n=s.length();
                if(n%k!=0)
                {
                    System.out.println("NO");
                }
                else
                {
                    HashMap<String, Integer> m = new HashMap<>();
                    for(int i=0;i<n;i+=k)
                    {
                        String x = s.substring(i,i+k);
                        int temp = m.get(s.substring(i,i+k))==null? 0 : m.get(s.substring(i,i+k));
                        m.put(s.substring(i,i+k), temp+1);
                    }
                    if(m.size()==1)
                    {
                        System.out.println("YES");
                    }
                    else if(m.size()==2)
                    {
                        int flag=0;
                        for(Map.Entry<String, Integer> e : m.entrySet())
                        {
                            if(e.getValue()==1)
                            {
                                flag=1;
                                break;
                            }
                        }
                        if(flag==0)
                        {
                            System.out.println("NO");
                        }
                        else
                        {
                            System.out.println("YES");
                        }
                    }
                    else
                    {
                        System.out.println("NO");
                    }
                }
  } 
} 
abcdabab
YES

Анализ сложности для преобразования строки, которая является повторением подстроки длины K  

Сложность времени

О (п) в котором n размер данной строки «s». Здесь мы просто формируем подстроку (от 0 до k-1, от k до 2k-1, от 2k до 3k-1 и так далее) ok длиной k и подсчитываем их частоту с помощью хэш-карты. Здесь мы делаем это за линейное время.

Космическая сложность

О (п) в котором n размер данной строки «s». Здесь мы используем хэш-карту для хранения количества подстроки длины k.