生成一个字符串,其所有K大小的子字符串都可以串联形成给定的字符串

2021年4月28日19:44:05 发表评论 1,018 次浏览

本文概述

给定一个大小为N的字符串串和一个整数K,任务是生成一个字符串,其大小为K的子串可以连接成给定的字符串。

例子:

输入:str ="abbaaa" K = 2
输出:abaa
说明:
父字符串"abaa"的大小为2的所有子字符串均为"ab", "ba"和"aa"。连接所有这些子字符串后, 可以获得给定的字符串"abbaaa"。
输入:str ="abcbcscsesesesd" K = 3
输出:abcsesd
说明:
父字符串"abcsesd"的大小为3的所有子字符串均为"abc", "bcs", "cse", "ses"和"esd"。连接所有这些子字符串后, 可以获得给定的字符串"abcbcscsesesesd"。

方法:

请按照以下步骤解决问题:

  1. 我们可以通过串联长度子串来清楚地观察到ķ, 除了第一个字符外, 其余K-1下一个子字符串中也将包含任何子字符串的字符。
  2. 因此, 遍历字符串并将每个子字符串的第一个字符附加到安斯然后忽略下一步K-1字符。
  3. 对除最后一个子字符串以外的所有子字符串重复此过程。
  4. 将最后一个子字符串的所有字符附加到安斯.
  5. 返回ans作为所需的解码字符串。

下面是上述方法的实现:

C ++

//C++ program to generate a 
//string whose substrings of
//length K concatenates to 
//form given strings
  
#include <bits/stdc++.h> 
using namespace std;
  
//Function to return the required 
//required string 
void decode_String(string str, int K)
{
     string ans = "" ;
     //Iterate the given string
     for ( int i = 0; i <str.size(); 
     i += K)
         //Append the first 
         //character of every 
         //substring of length K
         ans += str[i];
  
     //Consider all characters 
     //from the last substring
     for ( int i = str.size() - (K - 1); 
     i <str.size(); i++)
         ans += str[i];
  
     cout <<ans <<endl;
}
  
//Driver Program
int main()
{
     int K = 3;
     string str = "abcbcscsesesesd" ;
     decode_String(str, K);
}

Java

//Java program to generate a 
//string whose substrings of 
//length K concatenates to 
//form given strings 
class GFG{
      
//Function to return the required 
//required string 
public static void decode_String(String str, int K) 
{ 
     String ans = "" ; 
      
     //Iterate the given string 
     for ( int i = 0 ; 
             i <str.length(); i += K) 
         
        //Append the first 
        //character of every 
        //substring of length K 
        ans += str.charAt(i); 
      
     //Consider all characters 
     //from the last substring 
     for ( int i = str.length() - (K - 1 );
             i <str.length(); i++) 
        ans += str.charAt(i); 
      
     System.out.println(ans);
} 
  
//Driver code
public static void main(String[] args)
{
     int K = 3 ; 
     String str = "abcbcscsesesesd" ;  
      
     decode_String(str, K); 
}
}
  
//This code is contributed by divyeshrabadiya07

Python3

# Python3 program to generate a 
# string whose substrings of
# length K concatenates to 
# form given strings
  
# Function to return the required 
# required string 
def decode_String(st, K):
  
     ans = ""
      
     # Iterate the given string
     for i in range ( 0 , len (st), K):
          
         # Append the first 
         # character of every 
         # substring of length K
         ans + = st[i]
  
     # Consider all characters 
     # from the last substring
     for i in range ( len (st) - (K - 1 ), len (st)):
         ans + = st[i]
  
     print (ans)
  
# Driver code
if __name__ = = "__main__" :
      
     K = 3
     st = "abcbcscsesesesd"
      
     decode_String(st, K)
  
# This code is contributed by chitranayal

C#

//C# program to generate a string
//whose substrings of length K
//concatenates to form given strings 
using System;
  
class GFG{
      
//Function to return the required 
//required string 
public static void decode_String(String str, int K) 
{ 
     String ans = "" ; 
      
     //Iterate the given string 
     for ( int i = 0; 
             i <str.Length; i += K) 
              
         //Append the first 
         //character of every 
         //substring of length K
         ans += str[i]; 
      
     //Consider all characters 
     //from the last substring 
     for ( int i = str.Length - (K - 1);
             i <str.Length; i++) 
         ans += str[i]; 
      
     Console.WriteLine(ans);
} 
  
//Driver code
public static void Main(String[] args)
{
     int K = 3; 
     String str = "abcbcscsesesesd" ; 
      
     decode_String(str, K); 
}
}
  
//This code is contributed by Rohit_ranjan

输出如下:

abcsesd

时间复杂度:O(n)

辅助空间:O(1)


木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: