Exact Matches (with a Natural Key)
Your approach will be fundamentally different based on whether a Natural Key exists for the type of record your are trying to create.
A natural key is something that uniquely identifies a piece of data that already exists in the real world. For example, if your record has a Social Security Number, ISBN, Active Directory Account, or occasionally email / phone, you can prevent duplicates by guaranteeing each record has a distinct key.
For example, here's the sign up page on Twitter:

Note 1: As with any validation error, it's best to do so inline and immediately if the data state is invalid. So you should prompt for any unique information first, either in a stepper or seperate page in order to avoid any unnecessary typing.
Note 2: Bear in mind that you might NOT want to use email or phone as a unique identifier for contact records (for example, multiple professionals can all share the business contact email and phone number).
Note 3: While you can create your own sort of natural key, like a username, this isn't really a mechanism for prevent duplicates of anything but the generated name itself.
For example, here's the sign up page on Reddit:

This does a great job at dynamically showing validation errors as you type. However, the same user/person/individual can still create nearly identical accounts. Even though we've generated an identifier that will bear real world significance, it can only be used to differentiate accounts, not people.
Similar Matches
If we rely on multiple fields to establish a record AND genuine records can repeat information across fields (i.e. same First Name + Last Name + DOB), then the best any system can do is look to minimize the amount of duplicates, and technology can play a role in that business process.
Now the question becomes:
When is the most appropriate time to show users a list of similar looking records during the process of creating new records?
Option 1 - Synchronous / Modal Matches
When presenting potential duplicates in a synchronous fashion, you need to collect enough information to know about the incoming record and then have the user review potential matches before proceeding.
For example, here's the steps for adding new foods to My Fitness Pal:

Note 1: You should seed any search parameters into the new item if the user proceeds to creating a new record so they don't have to type the same info twice.
Note 2: How strongly you programmatically enforce the review will depend on the severity of duplicates and user telemetry from your actual system. For example, you could force scrolling / reviewing each one before proceeding to the actual creation step (like the TOC agreement on many sites).
Note 3: When identifying potential duplicates programatically, make sure to check for typos, nicknames, alternative spellings as well.
Option 2 - Asynchronous / Modeless Matches
This approach assumes the happy path and allows users to immediately begin entering record information, all of which becomes available for identifying potential matches asynchronously.
For Example, here's the steps for asking a question on Stack Overflow:

Note 1: When dynamically inserting potential matches (or any new content) onto the page, the content should come to the right or below the current page position to prevent the content from jumping and the user from having to regress back to a previous portion of the page.
In terms of choosing between synchronous and asynchronous checks, you might want to review your data of how often users successfully add new records without creating duplicates. If 80% of the time, users create unique records, then forcing them all through the duplicate check bottleneck is an added pain point and needless context shift.
Nothing forces users to actually read any information you put on the screen, so the goal should be to put something that looks and feels useful on the screen that will help them save time. And doing so requires really good matching algorithms without a lot of noise.
Deduplicate Records - Journey Mapping
If this is an important feature for your business, remember this need can also be addressed at multiple other interaction points. Certainly, it doesn't hurt to address during creation (GIGO), but you can manually deduplicate after the fact as well with functions for:
Individual Users
Put the power in the user's hands to review their own data quality, as per Google Contacts:
Community Reports
Ask for help from users to keep content clean (the wiki model), as in Untappd:
Moderated Review Queues
Ensure admins review system wide duplicates, as in Stack Exchange:

Further Reading: