Daily LeetCode punch – 100. Larger group position

“Offer comes, ask friends to take it! I am participating in the 2022 Spring Recruit Punch card campaign. Click here for more details.”

---

📢 preface

🚀 Algorithm 🚀

• 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
• 🌲 tip: the programming languages used in this column are C# and Java
• 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
• 🌲 today is the 100th day of continuous clocking of force button algorithm 🎈!

🚀 Algorithm 🚀

---

🌲 The location of a larger group

A string s consisting of lowercase letters contains groups consisting of consecutive identical characters.

For example, the string s = “abbXXXXzyy” contains groups such as “A “,” BB “, “XXXX “,” Z “and” YY “.

A group can be represented by an interval [start, end], where start and end indicate the subscripts of the start and end positions of the group, respectively. The “XXXX” group in the above example is represented by the interval [3,6].

We call all groups that contain more than three consecutive characters a larger group.

Find each larger grouping interval, sort it in ascending order by starting position, and return the result.

Example 1:

Enter: s ="abbxxxxzzy"Output: [[3.6]] :"xxxx"Is a beginning3And ends with6Larger grouping of.Copy the code

Example 2:

Enter: s ="abc"Output: [] Explanation:"a"."b" 和 "c"Are not large groups that meet the requirements.Copy the code

Example 3:

Enter: s ="abcdddeeeeaabbbcd"Output: [[3.5], [6.9], [12.14[] the larger group is"ddd"."eeee" 和 "bbb"
Copy the code

Example 4:

Enter: s ="aba"Output: []Copy the code

Tip:

• 1 <= s.length <= 1000
• The s contains only lowercase letters

---

🌻C# method: loop through

A double loop makes logical judgments

Code:

public class Solution
{
    public IList<IList<int>> LargeGroupPositions(string s)
    {
        var ans = new List<IList<int> > ();int index = 0;
        while (index < s.Length)
        {
            int start = index;
            while (index < s.Length && s[index] == s[start]) index++;
            if (index - start >= 3)
                ans.Add((new int[] { start, index - 1 }).ToList());
        }
        returnans; }}Copy the code

The execution result

By execution time:128Ms, in all CDefeated 57.14% of users in # submissionMemory consumption:41.9MB, in all CBeat 35.70% of users in # submission
Copy the code

---

🌻Java method: traversal once

We can iterate through the sequence and record the length of the current group.

If the next character is different from the current character or is already enumerated to the end of the string, the current character is the end of the current group.

Each time we find the end of the current group, if the group is 33 in length, we add it to the answer.

Code:

class Solution {
    public List<List<Integer>> largeGroupPositions(String s) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        int n = s.length();
        int num = 1;
        for (int i = 0; i < n; i++) {
            if (i == n - 1|| s.charAt(i) ! = s.charAt(i +1)) {
                if (num >= 3) {
                    ret.add(Arrays.asList(i - num + 1, i));
                }
                num = 1;
            } else{ num++; }}returnret; }}Copy the code

The execution result

By execution time:2Ms, beat out all Java commits16.41% user memory consumption:38.4MB, beat out all Java commits76.53% of the userCopy the code

Complexity analysis

Time: O(n) Space: O(1) 
Copy the code

---

💬 summary

• Today is the 100th day of the buckle algorithm clocking!
• The article USES theC# andJavaTwo programming languages to solve the problem
• Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
• That’s the end of today’s algorithm sharing, see you tomorrow!