java - 使用循环创建子字符串

Question

给定一个字符串，我必须从中找出满足以下条件的子字符串

• 子字符串中的所有字符都相同。例如:aa、bbb、cccc。

• 除中间字符外的所有字符都必须相同。例如:aba、bbabb等

我做了一个类似这样的算法

我使用两个循环来读取字符串，第一个循环保存第一个字符，第二个循环遍历字符串。

然后我将子字符串发送到 vet() 以查看子字符串是否包含小于或等于两个字符。如果子字符串包含两个字符，那么我检查它是否是回文

public static int reverse(String s)
    {
        String wrd="";
        for(int i = s.length()-1 ;i>=0;i--)
            wrd = wrd + s.charAt(i);

        if(s.equals(wrd))
            return 1;
        else
            return 0;

    }

    public static boolean vet(String s)
    {
        HashSet<Character> hs = new HashSet<>();
        for(char c : s.toCharArray())
        {
            hs.add(c);
        }
        if(hs.size() <= 2)
            return true;
        else
            return false;
    }

    static long substrCount(int n, String s) {
        List<String> al = new ArrayList<>();

        for(int i=0;i<s.length();i++)
        {
            for(int j=i;j<s.length();j++)
            {
                        if(vet(s.substring(i,j+1)))
                        {
                            if(reverse(s.substring(i,j+1)) == 1)
                                al.add(s.substring(i,j+1));
                        }

            }
        }
        return al.size();
    }

此代码对于小字符串工作正常，但是如果字符串很大(例如一万个字符)，此代码将抛出时间限制异常。

我怀疑破坏字符串并在 substrCount() 中创建子字符串的循环导致了时间复杂度，因为它具有嵌套循环。

请检查此代码并提供更好的方法来破坏字符串，或者如果由于其他部分而导致复杂性增加，请告诉我。

链接:https://www.hackerrank.com/challenges/special-palindrome-again/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=strings

Answer 1

• 您可以将字符串左侧和右侧的计数收集到 2 个单独的数组中。
• 现在，我们以以下方式收集计数:如果前一个字符等于当前字符，则将计数增加 1，否则将其设置为 1。

示例:

a  a  b  a  a  c  a  a

1  2  1  1  2  1  1  2 // left to right
2  1  1  2  1  1  2  1 // right to left

• 对于所有字符都相等的字符串，我们只是在迭代自身时收集所有字符。

• 对于除了中间字符之外全部相等的字符串，可以使用上面的表格，可以收集如下字符串:

伪代码:

if(str.charAt(i-1) == str.charAt(i+1)){ // you will add checks for boundaries
    int min_count = Math.min(left[i-1],right[i+1]);
    for(int j=min_count;j>=1;--j){
        set.add(str.substring(i-j,i+j+1));
    }
}

更新:

以下是我接受的解决方案。

static long substrCount(int n, String s) {
    long cnt = 0;
    int[] left  = new int[n];
    int[] right = new int[n];
    int len = s.length();
    for(int i=0;i<len;++i){
        left[i] = 1;
        if(i > 0 && s.charAt(i) == s.charAt(i-1)) left[i] += left[i-1];
    }

    for(int i=len-1;i>=0;--i){
        right[i] = 1;
        if(i < len-1 && s.charAt(i) == s.charAt(i+1)) right[i] += right[i+1];
    }

    for(int i=len-1;i>=0;--i){
        if(i == 0 || i == len-1) cnt += right[i];
        else{
            if(s.charAt(i-1) == s.charAt(i+1) && s.charAt(i-1) != s.charAt(i)){
                cnt += Math.min(left[i-1],right[i+1]) + 1;
            }else if(s.charAt(i) == s.charAt(i+1)) cnt += right[i];
            else cnt++;
        }
    }

    return cnt;
}

算法:

• 该算法与上面解释的相同，但有一些额外的内容。
• 如果字符位于边界，请输入 0或在 len-1 ，我们只看 right[i]计算字符串，因为我们没有 left在这里。

• 如果字符在此边界内，我们将进行如下检查:

  • 如果前一个字符等于下一个字符，我们检查前一个字符是否不等于当前字符。我们这样做是因为，我们希望避免将来在当前迭代本身添加字符串(例如像 aaaaa 这样的字符串，我们位于中间 a )。
  • 第二个条件是 s.charAt(i) == s.charAt(i+1) ，意思是，我们再次有像 aaa 这样的字符串我们是第一个 a 。所以我们只需添加 right[i]指示添加类似 a 的字符串, aa , aaa )。
  • 第三个是 cnt++意思是添加个性。

• 您可以进行一些优化，例如完全避免 right数组等，但我把它留给你作为练习。

• 时间复杂度:O(n)，空间复杂度:O(n)