首頁  >  文章  >  後端開發  >  最小改動字串使得所有子字串都不相同

最小改動字串使得所有子字串都不相同

王林
王林轉載
2023-09-04 14:49:07683瀏覽

最小改動字串使得所有子字串都不相同

字串是一種特定的對象,它表示資料字元的序列和流動。字串是一種資料容器,總是以文字格式表示。它也用於概念、比較、拆分、連接、替換、修剪、長度、內部化、相等、比較和子字串操作。子字串()是一種資料精煉過程,它從開始到結束提取保存的資料之間的資料。子字串()不會改變原始字串。在資料集中,當我們有不同的字元時,它們可以被表示為不同的資料元素。例如:'a'和'r'是不同的,而'r'和'r'是相同的。所以,一個字串比如說,橘子包含6個不同的字元。同樣,字串蘋果只包含4個不同的字元。

假設,"s" 是一個字串,我們需要找到所有子字串所需的最小改變次數,以使字串變得不同。

  • 字串的長度 - 26

  • 給定輸入− T 是第一行的測試案例,為一個整數。對於每個測試案例,只會有一行包含26個字元。

  • 輸出 - 我們將獲得每個測試案例的最小變化次數。

  • 邏輯方法流程的限制

    • 1

    • 1

在今天的文章中,我們將學習如何修改字串以使所有子字串都不同。

使子字串不同的演算法

這是一種可能的演算法,用於對字串進行操作,使得所有子字串都是不同的,同時盡量減少改變。

  • 第一步-開始。

  • 第二步− 使用兩個巢狀循環來產生子字串。

  • 第三步 - 外循環從 i = 0,字串長度減1。

  • 第4步 - 內循環從 j = 0,字串長度減1。

  • 第五步− 使用零值建立計數變數。

  • 步驟6− 在外部迴圈內部,建立一個distinct_character變數。

  • 第7步-建立頻率數組。

  • Step 8− Set all elements zero.

  • 第9步 - 檢查字串[j] - 'a'的頻率是否為零。

  • 步驟10− 如果為零,則將其增加1。

  • 步驟11− 否則,將其分解為內部循環。

  • 第12步- 如果計數大於零,則傳回計數。

  • 第13步- 否則,返回-1。

  • 第14步- 終止。

建立所有不同子字串的語法

string.substring(start, end)

在這個語法中,我們可以看到如何對一個字串進行最小的更改,使得所有的子字串都不相同。

  • 參數

    • 開始 - 需要宣告一個起始位置。這裡的第一個字元的索引是0。

    • End − 它是一個可選的過程,位於結束位置(包括但不限於)。

方法

方法1−找到使字串的所有子字串都變成不同的最小更改次數。

找到最小的更改次數,使得字串的所有子字串都變得不同

在這個方法中,我們將學習如何讓所有的子字串都不同。在這裡,每個字元都必須不同。我們只需要找出字元的數量。如果字串的長度超過26,則我們只需要將其轉換為一個字串。在這裡,我們將在不同的語言環境中編寫相同的邏輯。

範例1:使用C

#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
int minChanges(string &str) {
   int n = str.length();
   if (n > MAX_CHAR)
   return -1;
   int dist_count = 0;
   int count[MAX_CHAR] = {0};
   for (int i = 0; i < n; i++) {
      if (count[str[i] - 'a'] == 0)
      dist_count++;
      count[(str[i] - 'a')]++;
   }
   return (n - dist_count);
}
int main() {
   string str = "aebaecedabbeedee";
   cout << minChanges(str);
   return 0;
}

輸出

11

範例2:透過使用Java

import java.lang.*;
import java.util.*;
public class tutorialspoint {
   static final int MAX_CHAR = 26;
   public static int minChanges(String str) {
      int n = str.length();
      if (n > MAX_CHAR)
      return -1;
      int dist_count = 0;
      int count[] = new int[MAX_CHAR];
      for(int i = 0; i < MAX_CHAR; i++)
      count[i] = 0;
      for (int i = 0; i < n; i++) {
         if(count[str.charAt(i)-'a'] == 0)
         dist_count++;
         count[str.charAt(i)-'a']++;
      }
      return (n-dist_count);
   }
   public static void main (String[] args) {
      String str = "aebaecedabbeedee";
      System.out.println(minChanges(str));
   }
}

輸出

11

範例1:使用Python

MAX_CHAR = [26]
def minChanges(str):

	n = len(str )
	if (n > MAX_CHAR[0]):
		return -1
	dist_count = 0
	count = [0] * MAX_CHAR[0]

	for i in range(n):
		if (count[ord(str[i]) - ord('a')] == 0) :
			dist_count += 1
		count[(ord(str[i]) - ord('a'))] += 1
	return (n - dist_count)
if __name__ == '__main__':
	str = "aebaecedabbeedee"
	print(minChanges(str))
	

輸出

11

結論

今天,在本文中,我們學習瞭如何透過最小的改變使所有子字串都不同。在這裡,我們透過在C 、Java和Python中遵循所述演算法創建了一些可能的程式碼。希望這能幫助您對這個主題有更全面的了解。

以上是最小改動字串使得所有子字串都不相同的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除