java 找出字符串中最长的相同字符序列

Find the longest sequence of same characters in a string

提问by Snail

This code supposed to output the longest run on which a character in a string has a consecutive runs of itself. Though the problem is that it outputs: 8(which should be 5instead). I just would like to ask what seems to be the problem regarding this code.

此代码应该输出最长的运行，其中字符串中的字符具有连续运行。虽然问题在于它输出：8（应该是5）。我只是想问一下这段代码似乎有什么问题。

public class Sample {
    public static void main(String[] args) {
        String setofletters = "aaakkcccccczz"; /* 15 */
        int output = runLongestIndex(setofletters);
        System.out.println("Longest run that first appeared in index:" + output);
    }

    public static int runLongestIndex(String setofletters) {
        int ctr = 0;
        int ctrstor = 0;
        int ii = 0;
        int output = 0;

        // loops until the last character in the string
        for (int i = 0; i < setofletters.length() - 1; i++) {
            // checks if the letter is the same to the next
            if (setofletters.charAt(i) == setofletters.charAt(i++)) {
                ctr++;
                ii = i++;
                // loops until the letter in the index is no longer equal
                while (setofletters.charAt(i) == setofletters.charAt(ii)) {
                    ii++;
                    ctr++;
                }

                if (ctr > ctrstor) {
                    output = i;
                }
                // storing purposes
                ctrstor = ctr;
            }
            // resets the counter
            ctr = 0;
        }
        return output;
    }
}

回答by Karthik

UPDATESorry, I misunderstood your question a bit, you need to make the following changes in your code to make it work.(lines with comments)

更新抱歉，我有点误解了您的问题，您需要在代码中进行以下更改才能使其正常工作。（带注释的行）

   public static int runLongestIndex(String setofletters){
    int ctr = 1; // every character is repeated at least once, so you should initialize it to 1, not 0
    int ctrstor = 0;
    int ii = 0;
    int output = 0;

    for (int i = 0; i < setofletters.length() - 1; i++) {
        if (i < setofletters.length() - 1 && setofletters.charAt(i) == setofletters.charAt(i+1)) { // i++ is not same as i+1
            ctr++;
            ii = i+1; // i++ is not same as i+1
            while (setofletters.charAt(i) == setofletters.charAt(ii)) {
                ii++;
                ctr++;
            }

            if (ctr > ctrstor) {
                output = i;
            }
            ctrstor = ctr;
        }
        ctr = 1; // for the same reason I mentioned above
    }
    return output;
}

EDIT: the easiest way to write your code is :

编辑：编写代码的最简单方法是：

public static int runLongestIndex(String setofletters){ 
   int ctr = 1;
    int output = 0;
    int j=0;
    for(int i=0; i<setofletters.length()-1;i++){
        j=i;
        while(i <setofletters.length()-1 && setofletters.charAt(i)==setofletters.charAt(i+1)){
            i++;
            ctr++;
        }
        if(ctr>output){
            output=j;
        }
        ctr = 1;
    }
    return output;
}

Why are you assigning ito output? You should assign ctrto output.

为什么要分配i给输出？您应该分配ctr给output.

change

改变

   if(ctr>ctrstor){
      output=i;
   }

to

到

 if(ctr>ctrstor){
      output=ctr;
 }

and also I think you should change

而且我认为你应该改变

 if(setofletters.charAt(i)==setofletters.charAt(i++))

to

到

 if(i<setofletters.length()-1 && setofletters.charAt(i)==setofletters.charAt(i+1)){

and you should intialize ctrto 1but not 0because every character is repeated at least once.

并且您应该初始化ctr为1但不是0因为每个字符至少重复一次。

回答by Paolo Angioletti

I'll give you a Scala implementation for that problem.

我将为您提供针对该问题的 Scala 实现。

Here it is the automatic test (in BDD style with ScalaTest)

这是自动测试（使用 ScalaTest 的 BDD 风格）

import org.scalatest._
class RichStringSpec extends FlatSpec with MustMatchers {
  "A rich string" should "find the longest run of consecutive characters" in {
    import Example._
    "abceedd".longestRun mustBe Set("ee", "dd")
    "aeebceeedd".longestRun mustBe Set("eee")
    "aaaaaaa".longestRun mustBe Set("aaaaaaa")
    "abcdefgh".longestRun mustBe empty
  }
}

Following is the imperative style implementation, with nested loops and mutable variables as you would normally choose to do in Java or C++:

以下是命令式风格的实现，带有嵌套循环和可变变量，您通常会选择在 Java 或 C++ 中执行：

object Example {
  implicit class RichString(string: String) {
    def longestRun: Set[String] = {
      val chunks = mutable.Set.empty[String]
      val ilen = string.length
      var gmax = 0
      for ((ch, curr) <- string.zipWithIndex) {
        val chunk = mutable.ListBuffer(ch)
        var next = curr + 1
        while (next < ilen && string(next) == ch) {
          chunk += string(next)
          next = next + 1
        }
        gmax = chunk.length max gmax
        if (gmax > 1) chunks += chunk.mkString
      }
      chunks.toSet.filter( _.length == gmax )
    }
  }
}

Following is a functional-style implementation, hence no variables, no loops but tail recursion with result accumulators and pattern matching to compare each character with the next one (Crazy! Isn't it?):

下面是一个函数式的实现，因此没有变量，没有循环，而是带有结果累加器和模式匹配的尾递归以将每个字符与下一个字符进行比较（疯狂！不是吗？）：

object Example {
  implicit class RichString(string: String) {
    def longestRun: Set[String] = {
      def recurse(chars: String, chunk: mutable.ListBuffer[Char], chunks: mutable.Set[String]): Set[String] = {
        chars.toList match {
          case List(x, y, _*) if (x == y) =>
            recurse(
              chars.tail, 
              if (chunk.isEmpty) chunk ++= List(x, y) else chunk += y, 
              chunks
            )
          case Nil =>
            // terminate recursion
            chunks.toSet
          case _ => // x != y
            recurse(
              chars.tail,
              chunk = mutable.ListBuffer(), 
              chunks += chunk.mkString
            )
        }
      }
      val chunks = recurse(string, mutable.ListBuffer(), mutable.Set.empty[String])
      val max = chunks.map(_.length).max
      if (max > 0) chunks.filter( _.length == max ) else Set()
    }
  }
}

For example, for the given "aeebceeedd"string, both implementations above will build the following set of chunks (repeating characters)

例如，对于给定的"aeebceeedd"字符串，上面的两种实现都将构建以下组块（重复字符）

Set("ee", "eee", "dd")

and they will filter those chunks having the maximum length (resulting "eee").

他们将过滤那些具有最大长度的块（结果"eee"）。

回答by Tushar

This code should work for any length of string sequence.

此代码适用于任何长度的字符串序列。

public class LongestStringSequqnce {

static String myString = "aaaabbbbcccchhhhiiiiibbbbbbbbbccccccc";
static int largestSequence = 0;
static char longestChar = '
string = 'abbbccddddddddeehhhfffzzzzzzzzdddvyy'

longest_sequence = ''
for i in range(len(string)):
    is_sequence = True
    ch_sequence = ''
    while is_sequence:
        ch_sequence += string[i]
        if i+1 < len(string) and string[i]==string[i+1]:
            i += 1
        else:
            is_sequence = False
    if len(ch_sequence) > len(longest_sequence):
        longest_sequence = ch_sequence
print (longest_sequence)
';

public static void main(String args[]) {
    int currentSequence = 1;
    char current = '
def longestConsecutive(s: String): (Char, Int) = {
  Iterator.iterate(('\u0000', 0, 0)) { case (ch, longestRun, i) =>
    val run = (i until s.length)
      .takeWhile(s(_) == s(i))
      .size

    if (run > longestRun) (s(i), run, i + run)
    else (ch, longestRun, i + run)
  }
    .dropWhile(i => s.isDefinedAt(i._3))
    .take(1)
    .map(x => (x._1, x._2))
    .next()
}
';
    char next = '
("s", "ch", "n")
----------------
("", '\u0000', 0),
("a", 'a', 1),
("aabcddbbbea", 'b', 3),
("abcddbbb", 'b', 3),
("cbccca", 'c', 3)
';

    for (int i = 0; i < myString.length() - 1; i++) {
        current = myString.charAt(i);
        next = myString.charAt(i + 1);

        // If character's are in sequence , increase the counter
        if (current == next) {
            currentSequence += 1;
        } else {
            if (currentSequence > largestSequence) { // When sequence is
                                                     // completed, check if
                                                     // it is longest
                largestSequence = currentSequence;
                longestChar = current;
            }
            currentSequence = 1; // re-initialize counter
        }
    }
    if (currentSequence > largestSequence) { // Check if last string
                                             // sequence is longest
        largestSequence = currentSequence;
        longestChar = current;
    }

    System.out.println("Longest character sequence is of character "
            + longestChar + " and is " + largestSequence + " long");
}

}

Source : http://www.5balloons.info/program-java-code-to-find-longest-character-sequence-in-a-random-string/

来源：http: //www.5balloons.info/program-java-code-to-find-longest-character-sequence-in-a-random-string/

回答by DariaS

Well, the solution a bit depends on the additional requirements. Here is the code which returns the FIRST longest sequence of a repeated character int the given string, meaning if you have a second sequence with the same length you never get it out :(. But still, this is a simple and clear solution here, so good news - it works! :)

嗯，解决方案有点取决于额外的要求。这是返回给定字符串中重复字符的第一个最长序列的代码，这意味着如果你有第二个长度相同的序列，你永远不会得到它:(。但是，这仍然是一个简单而清晰的解决方案，好消息 - 它有效！:)

public static int runLongestIndex(String setofletters) {
  int maxCount = 0;
  int maxIndex = 0;

  // loops each character in the string
  for (int i = 0; i < setofletters.length() - 1; ) {
    // new char sequence starts here
    char currChar = setofletters.charAt(i);
    int count = 1;
    int index = i;
    while ( (index < setofletters.length() - 1) &&
            (currChar == setofletters.charAt(++index)) ) {
       count++;
    } 

    if (count > maxCount) {
       maxIndex = i;
       maxCount = count;
    }
    i = index;
  }
  return maxIndex;
}

回答by Abhijit Sarkar

@Paolo Angioletti already provided an answer using Scala, but it's more complicated than it needs to be. The idea is not very different from Run-length encoding. Time complexity O(n).

@Paolo Angioletti 已经使用 Scala 提供了一个答案，但它比它需要的要复杂。这个想法与Run-length encoding没有太大区别。时间复杂度O(n)。

public static int runLongestIndex(String setofletters) {
    if (setofletters == null || setofletters.isEmpty()) {
      return -1;
    }
    int cnt = 1;
    char prevC = setofletters.charAt(0);
    int maxCnt = 1;
    //char maxC = prevC;
    int maxRunIdx = 0;
    int curRunIdx = 0;
    for (int i = 1; i < setofletters.length(); i++){
      final char c = setofletters.charAt(i);
      if (prevC == c) {
        cnt++;
      } else {
        if (cnt > maxCnt) {
          maxCnt = cnt;
          //maxC = prevC;          
          maxRunIdx = curRunIdx;
        }
        cnt = 1;
        curRunIdx = i;
      }
      prevC = c;
    }
    if (setofletters.charAt(setofletters.length() - 1) == prevC) {
      if (cnt > maxCnt) {
        //maxC = prevC;
        maxCnt = cnt;
        maxRunIdx = curRunIdx;
      }
    }
    return maxRunIdx;
  }

Tested with:

测试：

    public static int count (String str) {
    int i = 0;
    while(i < str.length()-1 && str.charAt(i)==str.charAt(i+1))
        i ++;

    return ++i;

}
public static int getLongestIndex(String str){
    int output = 0;
    for(int i=0, cnt = 1, counter = 0 ; i<str.length() - 1;i += cnt, cnt = count(str.substring(i)), output = (counter = (cnt > counter ? cnt : counter)) == cnt ? i : output);
    return output;
}

回答by MaxZoom

There are few traps in the code that your logic felt in:

您的逻辑在代码中几乎没有陷阱：

1. Code incorrectly assumes that there is always next character to compare current one.
   This fails for string like "a"or the last character in any string.

2. Code does not store the max count of characters but only the max index (i).
   MaxCount is needed to compare the next chars sequence size.

3. Loop forand loop whilerepeat the same subset of characters.

4. Also variable name style makes it harder to understand the code.

1. 代码错误地假设总是有下一个字符来比较当前字符。
   对于类似字符串"a"或任何字符串中的最后一个字符，这将失败。

2. 代码不存储最大字符数，而只存储最大索引 ( i)。
   需要 MaxCount 来比较下一个字符序列大小。

3. 循环for和循环while重复相同的字符子集。

4. 变量名样式也使代码更难理解。

After correcting above

以上更正后

       char[] ar = str.toCharArray();
       int longestRun = 0;
       int lastLongestRun = 0;
       int index = 0;
       for(int i = ar.length-1; i>0; i--){
           if(ar[i] == ar[i-1]){
               longestRun++;
           }else{
               if(longestRun > lastLongestRun){
                   lastLongestRun = longestRun;
                   longestRun = 0;
                   index = i;
               }
           }
       }

       return index;

See Java DEMO

见 Java演示

回答by Lev

I think you don't need an internal loop:

我认为您不需要内部循环：

       if(ctr>ctrstor){
            output=i;
        }
        //storing purposes
        ctrstor=ctr;

and this code: System.out.println(runLongestIndex("aaakkcccccczz")); gives you 5

和这段代码： System.out.println(runLongestIndex("aaakkcccccczz")); 给你 5

回答by Criss

This is how a "colleague" of mine is understanding to write readable code in order to solve this problem, even if this is working :)

这就是我的“同事”理解编写可读代码以解决此问题的方式，即使这是有效的:)

##代码##

回答by Arvind Kumar Pandey

int indexOfLongestRun(String str) {

int indexOfLongestRun(String str) {

##代码##

回答by ControlAltDel

##代码##

This looks like the problem. So if you find 8 consecutive characters, it will set output to 8, and proceed. The next time thru, it finds 3 consecutive characters, so doesn't set output, but sets ctrstor. Next time thru it finds 4 consecutive characters, and this will set output to 4

这看起来像问题。所以如果你找到 8 个连续的字符，它会将输出设置为 8，然后继续。下一次通过，它找到了 3 个连续的字符，所以不设置输出，而是设置 ctrstor。下次通过它找到 4 个连续字符，这会将输出设置为 4