2023-11-10 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's November LeetCoding Challenge with cpp.

November LeetCoding Challenge 10

Description

Restore the Array From Adjacent Pairs

There is an integer array nums that consists of n unique elements, but you have forgotten it. However, you do remember every pair of adjacent elements in nums.

You are given a 2D integer array adjacentPairs of size n - 1 where each adjacentPairs[i] = [ui, vi] indicates that the elements ui and vi are adjacent in nums.

It is guaranteed that every adjacent pair of elements nums[i] and nums[i+1] will exist in adjacentPairs, either as [nums[i], nums[i+1]] or [nums[i+1], nums[i]]. The pairs can appear in any order.

Return the original array nums. If there are multiple solutions, return any of them.

 

Example 1:

Input: adjacentPairs = [[2,1],[3,4],[3,2]]
Output: [1,2,3,4]
Explanation: This array has all its adjacent pairs in adjacentPairs.
Notice that adjacentPairs[i] may not be in left-to-right order.

Example 2:

Input: adjacentPairs = [[4,-2],[1,4],[-3,1]]
Output: [-2,4,1,-3]
Explanation: There can be negative numbers.
Another solution is [-3,1,4,-2], which would also be accepted.

Example 3:

Input: adjacentPairs = [[100000,-100000]]
Output: [100000,-100000]

 

Constraints:

  • nums.length == n
  • adjacentPairs.length == n - 1
  • adjacentPairs[i].length == 2
  • 2 <= n <= 105
  • -105 <= nums[i], ui, vi <= 105
  • There exists some nums that has adjacentPairs as its pairs.

Solution

class Solution {
  const int MOD = 1e9 + 7;
public:
  int countHomogenous(string s) {
    int count = 0;
    int answer = 0;
    int current = s.front();
    for(auto c : s) {
      if(current == c) {
        count += 1;
      } else {
        answer += 1LL * count * (count + 1) / 2 % MOD;
        answer %= MOD;
        count = 1;
        current = c;
      }
    }
    answer += 1LL * count * (count + 1) / 2 % MOD;
    answer %= MOD;
    return answer;
  }
};

// Accepted
// 84/84 cases passed (24 ms)
// Your runtime beats 71.96 % of cpp submissions
// Your memory usage beats 53.48 % of cpp submissions (12 MB)
Algorithm