A string is good if there are no repeated characters.
Given a string s, return the number of good substrings of length three in s.
Note that if there are multiple occurrences of the same substring, every occurrence should be counted.
A substring is a contiguous sequence of characters in a string.
Example 1:
Input: s = "xyzzaz " Output: 1 Explanation: There are 4 substrings of size 3: "xyz ", "yzz ", "zza ", and "zaz ". The only good substring of length 3 is "xyz ".
Example 2:
Input: s = "aababcabc " Output: 4 Explanation: There are 7 substrings of size 3: "aab ", "aba ", "bab ", "abc ", "bca ", "cab ", and "abc ". The good substrings are "abc ", "bca ", "cab ", and "abc ".
Constraints:
1 <= s.length <= 100s consists of lowercase English letters.program main
implicit none
character(len=*), parameter :: input_format = "(A)"
character(len=:), allocatable :: s
integer :: n_good_substrings
call get_string(input_format, s)
n_good_substrings = count_good_substrings(s)
write (*, '(I0)') n_good_substrings
contains
function count_good_substrings(s) result(n)
implicit none
character(len=*), intent(in) :: s
integer :: i, j, k, n
do i = 1, len(s)-2
do j = i+1, len(s)-1
do k = j+1, len(s)
if (s(i:j) == s(j:k)) then
n = n + 1
end if
end do
end do
end do
end function count_good_substrings
subroutine get_string(fmt, str)
implicit none
character(len=*), intent(in) :: fmt
character(len=:), allocatable, intent(out) :: str
character(len=100) :: buffer
read (*, fmt) buffer
allocate(character(len=len_trim(buffer)) :: str)
str = trim(buffer)
end subroutine get_string
end program mainAt line 36 of file temp.f95 (unit = 5, file = 'stdin') Fortran runtime error: End of file Error termination. Backtrace: #0 0x78b6918be960 in ??? #1 0x78b6918bf4d9 in ??? #2 0x78b691b1317b in ??? #3 0x78b691b13752 in ??? #4 0x78b691b0ff1b in ??? #5 0x78b691b14e3c in ??? #6 0x78b691b15e55 in ??? #7 0x585076b9c2fb in get_string.0 #8 0x585076b9c576 in MAIN__ #9 0x585076b9c761 in main
module good_substrings
implicit none
contains
integer function count_good_substrings(s) result(count)
character(len=*), intent(in) :: s
integer :: i, j, k, n
count = 0
n = len(s)
do i = 1, n - 2
do j = i + 1, n - 1
do k = j + 1, n
if (s(i:j) == s(j:k) .and. s(j:k) /= s(i:j)) then
count = count + 1
end if
end do
end do
end do
end function count_good_substrings
end module good_substrings
program test_good_substrings
use good_substrings
implicit none
integer :: count
count = count_good_substrings("xyzzaz")
write (*,*) count
count = count_good_substrings("aababcabc")
write (*,*) count
end program test_good_substrings
0
0
from collections import deque
def highest_island(is_water):
m, n = len(is_water), len(is_water[0])
height = [[-1] * n for _ in range(m)]
q = deque()
for i in range(m):
for j in range(n):
if is_water[i][j] == 1:
height[i][j] = 0
q.append((i, j))
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
while q:
x, y = q.popleft()
for i in range(4):
newX = x + dx[i]
newY = y + dy[i]
if 0 <= newX < m and 0 <= newY < n and height[newX][newY] == -1:
height[newX][newY] = height[x][y] + 1
q.append((newX, newY))
return height
The algorithm works by performing a breadth-first search (BFS) from each water cell (value 1). It first initializes the height matrix with -1 for all cells, except water cells are assigned height 0. It then pushes all water cells to the queue. This queue is used for BFS.
Inside the while loop, we dequeue the cell and explore its neighbors. If a neighbor cell's height is -1 (which means it hasn't been visited yet), we assign it a height that is one more than the height of the current cell, then push the neighbor into the queue. By doing this for all cells in the queue, we will eventually assign every cell its maximum possible height.
The time complexity of this algorithm is O(mn) since the BFS processes each cell once.
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> highestIsland(vector<vector<int>>& isWater) {
int m = isWater.size();
int n = isWater[0].size();
vector<vector<int>> height(m, vector<int>(n, -1));
queue<pair<int, int>> q;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (isWater[i][j] == 1) {
height[i][j] = 0;
q.push({i, j});
}
}
}
vector<int> dx = {-1, 0, 1, 0};
vector<int> dy = {0, 1, 0, -1};
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (newX >= 0 && newX < m && newY >= 0 && newY < n && height[newX][newY] == -1) {
height[newX][newY] = height[x][y] + 1;
q.push({newX, newY});
}
}
}
return height;
}
The algorithm works by performing a breadth-first search (BFS) from each water cell (value 1). It first initializes the height matrix with -1 for all cells, except water cells are assigned height 0. It then pushes all water cells to the queue. This queue is used for BFS.
Inside the while loop, we dequeue the cell and explore its neighbors. If a neighbor cell's height is -1 (which means it hasn't been visited yet), we assign it a height that is one more than the height of the current cell, then push the neighbor into the queue. By doing this for all cells in the queue, we will eventually assign every cell its maximum possible height.
The time complexity of this algorithm is O(mn) since the BFS processes each cell once.