给定长度的子串中的最大元音数


在本文中,我们将研究一个与字符串和 Sliding-Window Algorithm相关的有趣问题。问题是 :"Given a String we have to Find the Maximum Number of Vowel Letters present in any Substring of the String, with the length of each Substring equal to K."

让我们通过一些示例输入来理解这个语句:

Input: String = "java2blog" K = 3
Output: 2
Explanation: The Substrings with length K=3 for the Given String are: "jav" , "ava", "va2", "a2b", "2bl", "blo", "log". Out of which the Substring "ava" has the maximum number of vowels i.e. 2.

Input: String = "looijk" K = 3
Output: 3 (Substring "ooi" has Maximum Vowel Letters).

现在,我们将讨论解决问题的不同方法并分析它们的复杂性。

方法 - 1 使用 substring() 方法生成所有子字符串

  • 基本上,我们将遍历字符串的长度并生成给定长度 K 的 所有子字符串使用包类中substring()存在的方法。String``java.lang

  • 我们保留一个变量 maxVowels,它将用于跟踪子字符串的最大元音。因此,对于每个子字符串,我们计算其中的元音数量并更新 maxVowels。

  • 为了计算子字符串中元音的数量,我们实现countVowelsInSubstring()了,一个给定子字符串的方法将返回其中元音的数量。

    让我们看一下这种方法的代码:

    public class MaxVowelsSubstring
    {
      static int maxVowelsInSubstring(String s,int k)
      {
          int n = s.length();
          int maxVowels = 0;
          // we iterate till n-k th position of the string
          for(int i = 0;i < n - k ;i++)
          {
            // We generate the substring of length k using substring().  
            String sub_s = s.substring(i,i+k);
            //then count the vowels in the substring
            int vowels = countVowelsInSubstring(sub_s);
            // update maxVowels if current vowels is greater.
            maxVowels = Math.max(maxVowels,vowels);
    
          }
    
          return maxVowels;
      }
    
      static int countVowelsInSubstring(String s)
      {
          int countVowels = 0;
          for(int i=0; i<s.length();i++)
          {
              //get current char
              char ch = s.charAt(i);
              // check if it is a vowel and increment count.              
              if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' )
              countVowels++;
          }
          return countVowels;
      }
    
      public static void main(String args[])
      {
          String str = "java2blog";
          int k = 3;
          int result = maxVowelsInSubstring(str,k);
    
          System.out.println("The Maximum Vowels present in the Substring of size "+k+" is : "+result);
      }
    
    }

    Output:

The Maximum Vowels present in the Substring of size 3 is : 2
Time Complexity:`使用方法生成大小为 K 的子字符串`substring()`需要 O(K) 时间,我们为 NK 个字符执行此操作需要总`O( (N-K) * K )`时间。现在,对于每个大小为 K 的子串,我们计算其中的元音,这需要总时间,所以总体 [时间复杂度](https://java2blog.com/introduction-to-complexity-of-algorithm/ “时间复杂度” ) 将是: . 对于这个问题,这是一个幼稚的解决方案。`O( K * K) = O(K2)``O( N*K -K2 + K2) = O(N * K)

方法 - 2 使用滑动窗口方法(线性时间解决方案)

这种方法背后的目的是为这个问题提供一个线性运行时解决方案(O(n))。为此,我们将使用滑动窗口方法的思想。我们遵循以下步骤:

  • 首先,我们将计算第一个大小为 K 的窗口中的元音数,即从索引 0 到 K-1 的元音数为countVowels。我们有一个变量maxVowels来跟踪窗口中元音的最大数量。
  • 如果第一个窗口有元音,我们更新 maxVowels。然后我们从索引 K 开始遍历字符串的长度并计算每个窗口中的元音。考虑字符串"java2blog",在字符串的不同窗口中出现的元音如下所示:

img

  • 我们使用前缀数组的思想,在获得第一个窗口中的元音后,我们从索引开始K,如果索引 K 处的字符是元音,我们增加countVowels,如果索引处的字符i - k是元音,我们减countVowels1。这个step 确保窗口在每次迭代中向右滑动。
  • 最后,我们maxVowels为我们处理的每个窗口更新 。

现在,让我们看一下上述方法在代码中的实现:

public class MaxVowelsSubstring
{
  static boolean isVowel(char ch)
  {
    if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
        return true;
    return false;
  }

  static int maxVowelsInSubstring(String s,int k)
  {
    int countVowels=0;  //Maintains overall count of vowels
    // Count vowels in First Window
    for(int i=0;i<k;i++)
    {
        if(isVowel(s.charAt(i)))
            countVowels++;
    }

    int maxVowels = 0;
    // Update maxVowels for first window.
    if(maxVowels< countVowels)
        maxVowels = countVowels;

    for(int i=k;i<s.length();i++)
    {
        if(isVowel(s.charAt(i)))          // check if current char is a vowel.    
            countVowels++;

        if(isVowel(s.charAt(i-k)))      // check if starting of previous window was a vowel
            countVowels--;

        maxVowels = Math.max(maxVowels,countVowels);   // update maxVowels for each window.
    }

    return maxVowels;
 }

  public static void main(String args[])
  {
      String str = "java2blog";
      int k = 3;
      int result = maxVowelsInSubstring(str,k);

      System.out.println("The Maximum Vowels present in the Substring of size "+k+" is : "+result);
  }

}

Output:

The Maximum Vowels present in the Substring of size 3 is : 2

Time Complexity:基本上,我们在字符串 N 的长度上滑动窗口,并且只遍历每个字符一次。对于每个字符,我们检查它是否是一个 O(1) 操作的元音。所以这种方法的时间复杂度是O(N)并且给出了问题的最佳解决方案。

这就是给定长度的子字符串中元音的最大数量,您可以尝试使用考虑所有边缘情况的不同示例的代码。


原文链接:https://codingdict.com/