資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究由前 K 個字母組成的最大長度的字典序最小的字串，該字串不包含任何重複的子字串
在這個問題中，我們需要使用字母表的前 K 個字元生成一個字典序最小的字串，以便它不包含任何重複的子字串。我們可以生成一個字串，使所有長度為 2 的子字串都是唯一的。因此，如果所有長度為 2 的子字串都是唯一的，則所有長度為 3 或更長的子字串也是唯一的。
問題陳述 - 我們給定一個正整數 K。我們需要使用前 K 個字母生成一個新字串，以便生成的字串不能包含任何長度為 2 或更長的重複子字串，並且是字典序最小的。
示例
輸入 - K = 1
輸出 - ‘aa’
解釋 - 我們可以只使用 'a' 生成 'aa'，以便生成的字串包含所有長度為 2 或更長的唯一子字串。
輸入 - K = 2
輸出 - ‘aabba’
解釋 - 'aabba' 是我們可以僅使用 'a' 和 'b' 生成的字典序最小的字串。
輸入 - K = 4
輸出 - ‘aabacadbbcbdccdda’
解釋 - 'aabacadbbcbdccdda' 是我們可以使用前 4 個字母字元生成的最小字串。
方法 1
此方法將使用兩個巢狀迴圈來生成一個包含長度為 2 的唯一子字串的新字串。
演算法
用空字串初始化 'str' 變數。
在 97 到 97 + k 的範圍內迭代，其中 97 是 'a' 的 ASCII 值。
將當前字元追加到 'str' 中。
在 I 到 97 + k 的範圍內迭代。
將 i 和 j 轉換為字元值並追加到 str 中。
當兩個巢狀迴圈的迭代完成時，在 str 的末尾追加 'a'。
返回 str，它是使用前 K 個字母生成的新字串。
示例
#include <bits/stdc++.h>
using namespace std;
// function to return the lexicographically smallest string of length K
string getTheString(int K){
// to store the resultant string
string str = "";
// Iterating over the range [97, 97 + K]
for (int i = 97; i < 97 + K; i++){
// appending the ith character to the string
str = str + char(i);
// Create a substring of length 2 consisting of the ith character and the jth character
for (int j = i + 1; j < 97 + K; j++){
// appending i and j to str
str += char(i);
str += char(j);
}
}
// appending the last character to the string
str += char(97);
// return the resultant string
return str;
}
int main(){
int K = 2;
cout << "The lexicographically smallest string is " << getTheString(K);
return 0;
}
輸出
The lexicographically smallest string is aabba
時間複雜度 - O(K * K)，因為兩個迴圈都遍歷前 K 個字元。
空間複雜度 - O(K * K)，因為我們將新生成的字串儲存到 'str' 變數中。
在上面的程式碼中，我們使用前 k 個字元生成所有長度為 2 的唯一子字串。我們需要建立唯一的字元對來建立長度為 2 的唯一子字串，並且該邏輯在解決方案方法中遵循。
298 次檢視
